这篇文章讲邻接表讲的很好。记录一下自己的理解。

邻接表用的是链式存储结构，根据图很好理解，但是一看代码就懵了。拿原文提到的一个数据举例：

4 5

1 4 9

4 3 8

1 2 5

2 4 6

1 3 7

四个顶点5条边，自然可以先拿u[],v[],w[]数组记录每条边，因为要用数组模拟链表，所以想到可以开两个数组first[],next[]（初始化都为-1），first[]存的是以顶点为起始点的最后一条边。比如first[1]=5,因为顶点1最后在第5条边且为初始点。那么前面还有1的边怎么办呢？就用next[]数组记录这个点所在的上一条边，所以next[5]=3,next[3]=1,即顶点1最后在5号边，5号边上一个包含顶点1的边是3号边等等。。

大概写个代码：

1 int maxn=100; 2 int v[maxn],u[maxn],w[maxn],first[maxn],next[maxn]; 3 int n,m,a,b,c; 4 cin>>n>>m; 5 for(int i=1;i<=n;i++) first[i]=-1; 6 for(int i=1,i<=m;i++){ 7     cin>>u[i]>>v[i]>>w[i]; 8     next[i]=first[u[i]];//i号边所在顶点的上一条边是first[u[i]]号边 9     first[u[i]]=i;//以u[i]为起始顶点的最后一条边是i号边10 }

 看来这些东西还要靠自己悟。其实用指针实现更好理解：

1 typedef struct edge//邻接表中的边 2 { 3     int objectPoint;//边的另一端点 4     int edgeLength;//边长 5     struct edge *nextEdge;//指向下一条边 6 }Edge; 7  8 typedef struct point//邻接表中的点 9 {10     int data;//点的编号11     struct edge *firstEdge;//指向该点后接单链表的第一条边12     struct edge *lastEdge;//该指针在用尾插法时才用，指向该点后接单链表的最后一条边13 }Point;14 15 Point G[N];//G是原图16 17 int main()18 {19     while(cin>>a>>b>>c)//输入边a,b和权值c。头插法。20     {21         Edge *p;22         p->obcjectPoint=b;23         p->edgeLength=c;24         p->nextEdge=G[a].firstEdge;25         G[a].firstEdge=p;26         Edge *p;27         p->obcjectPoint=a;28         p->edgeLength=c;29         p->nextEdge=G[b].firstEdge;30         G[b].firstEdge=p;31     }32     return 0;33 }