首页 > 其他 > 详细

链式前向星

时间:2019-02-13 00:55:09      阅读:91      评论:0      收藏:0      [点我收藏+]

标签:using   head   gcd   i++   包括   set   define   style   def   

链式前向星

图的存储一般有两种:邻接矩阵、邻接表(邻接表包括一种东西叫前向星)。

若图是稀疏图,边很少,开二维数组a[][]很浪费;

若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.

前向星的效率不是很高,优化后为链式前向星,直接介绍链式前向星。

(一)链式前向星
 

1. 结构

这里用两个东西:

1 结构体数组edge存边,edge[i]表示第i条边,

2 head[i]存以i为起点的最后一条边(在edge中的下标)

struct node{
    int next;   //下一条边的存储下标(默认0) 
    int to;     //这条边的终点 
    int w;      //权值 
}; 
node edge[500010];

 

2.增边

若以点i为起点的边新增了一条,在edge中的下标为j.

那么edge[j].next=head[i];然后head[i]=j.

即每次新加的边作为第一条边,最后倒序遍历

void add(int u, int v, int w) {  //起点u, 终点v, 权值w 
    //cnt为边的计数,从1开始计 
    edge[++cnt].next = head[u];
    edge[cnt].w = w;
    edge[cnt].to = v;
    head[u] = cnt;    //第一条边为当前边 
} 

 

3. 遍历

遍历以u为起点的边

for(int i=head[u]; i!=0; i=edge[i].next)

 

链式前向星实现SPFA

#include <cstdio>
#include <map>
#include <iostream>
#include<cstring>
#include<bits/stdc++.h>
#define ll long long int
#define M 6
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
struct node{
    int next;
    int to;
    int w;
};
node edge[100007];
int n, m, u, cnt;
int head[100007];
int dis[100007];
bool vis[100007];
void add(int u, int v, int w) {
    edge[++cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
}
void spfa(int x){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    dis[x]=0;
    memset(vis,0,sizeof(vis));
    queue<int > q;
    q.push(x);
    vis[x]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=0;i=edge[i].next){
            int to=edge[i].to; int d=edge[i].d;
            if(dis[to]>dis[u]+d){
                dis[to]=dis[u]+d;
                if(!vis[to]){
                    q.push(to);
                    vis[to]=1;
                }
            }
        }
    }        
}
int main(){
    
}

 

链式前向星

标签:using   head   gcd   i++   包括   set   define   style   def   

原文:https://www.cnblogs.com/wmj6/p/10367671.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号