图的邻接表表示法 （非指针实现）

图的邻接表表示法（一）
邻接表储存图结构本质上是将图上的每条边都储存起来
我们希望通过边被添加的顺序序号来储存边
假设(1,2)是第一条被添加的边，(1,4)是第四条，(1,3)是第五条，他们是关联1的所有边
即edge[0].u=1;edge[0].v=2
edge[3].u=1;edge[3].v=4
edge[4].u=1;edge[4].v=5

我们希望
edge[0].next=-1;
edge[3].next=0;
edge[4].next=3;
head[1]=4;
从而实现链式顺序

下面给出完整的邻接表模板

//邻接表模板
const int maxe;
const int maxv;

struct graph{
    int ne,nv;
    int head[maxe];
    struct edgenode{
        int v,w,next;
    }edge[maxe]; 
    
    void addedge(int u,int v,int w){
        edge[ne].v=v;
        edge[ne].w=w;
        edge[ne].next=head[u];
        head[u]=ne++;
        //建立反向边 
        edge[ne].v=u;
        edge[ne].w=w; //假设反向边的权值相同 
        edge[ne].next=head[v];
        head[v]=ne++;
    }
    
    void build(int n,int e){
        nv=n;
        memset(head,-1,sizeof(head));
        ne=0;
        int x,y,z;
        for(int i=0;i<e;i++)
        {
            cin>>x>>y>>z;
            x--;y--;       //表示图的下标从0开始 
            addedge(x,y,z);
        }
    }
}g;

图的邻接表表示法二（用vector更简单的表示法）

一条边（u,v）的表示
graph[u][ 0--adj[u] ]=v;

//由于该方法只储存邻接顶点而未储存边，所以此方法在带权图中不适用
#include<vector>
vector<int>graph[n];
int adj[n];
void addedge( int u,int v,int w ){
　　graph[u].push(v);

　　adj[u]++;
}

//取得u的邻接节点
for(int i=0;i<adj[u];i++){
　　visit(graph[u][i]);
}