我们之前介绍过图的邻接矩阵存储方式。其空间复杂度和时间复杂度均为N2。现在我再介绍一个。图的一种存储方式：邻接表，这样空间复杂度和时间复杂度都是M。对于稀疏图，M远小于N2。先上传数据，如下。第45149438125246137***行包含两个整数nm。n代表顶点数（顶点编号从1到n），m代表边数。接下来m行表示每行有3个数xyz，表示从顶点x到顶点y的边的权重为z。下图是使用链表实现邻接表的方法。上述实现方法为图中的每个顶点（左部分）创建了一个单向链表（右部分）。这样我们就可以通过遍历每个顶点的链表得到该顶点的所有边。使用链表来实现邻接表对于讨厌指针的朋友来说简直就是噩梦。这里介绍另一种使用数组实现的邻接表，在实际应用中是一种非常容易实现的方法。该方法还为每个顶点i（i从1到n）保存了一个“链表”，其中存储了从顶点i开始的所有边，如下所示。首先，我们按照读取的顺序对每条边(1~m)进行编号。比如第一条边“149”的个数是1，“137”的边个数是5。这里用u,v,w三个数组来记录具体的信息每条边，即u[i]、v[i]、w[i]表示第i条边是从第u[i]个顶点到Vertexv[i]（u[i]àv[i]),权重为w[i]。然后使用第一个数组存储每个顶点的一条边的数量。以至于我们后面会枚举每个顶点的所有边（你可能会问：存储其中一条边的编号就够了吗？不可能，每个顶点都需要存储它所有边的编号！别着急，继续往下看）。例如顶点1有一条边“149”（这条边的编号为1），则将first[1]的值设置为1。如果顶点i没有从该顶点开始的边，则设置值从first[i]到-1。现在让我们看看它是如何工作的。初始状态如下。嗯？为什么上图中多了一个next数组，作用是什么？别着急，后面我会解释，现在读第一条边“149”。读入第一条边（149），将这条边的信息存入u[1]、v[1]、w[1]。同时给这条边赋一个编号，因为这条边是最晚读入的，存放在u、v、w数组中下标为1的单元格中，所以编号为1。这条边是顶点1，所以把first[1]的值设为1。另外，这条“编号为1的边”是从顶点1开始的第一条边（即u[1]），所以next[1]的值]应设置为-1。也就是说，如果当前的“编号为i的边”是我们找到的第一条以u[i]为起点的边，则将next[i]的值设置为-1（貌似这个next数组很玄乎⊙_⊙).读入第二条边（438），将这条边的信息存入u[2]、v[2]和w[2]中，这条边的编号为2。这条边的起始顶点为vertex4号，所以将first[4]的值设置为2。另外，这条“编号为2的边”是我们从4号顶点开始找到的第一条边，所以将next[2]的值设置为-1.读入第三条边（125），将这条边的信息存入u[3]、v[3]和w[3]中，这条边的编号为3，起始顶点为1号顶点。我们发现顶点1已经有一条“编号为1的边”。如果此时把first[1]的值设置为3，那“编号为1的边”不就丢失了吗？我有个办法，这个时候把next[3]的值设为1就行了。现在你知道下一个数组是做什么用的了。next[i]存储“编号为i的边”的“前一条边”的编号。读入第四条边（246），将这条边的信息存入u[4]、v[4]和w[4]中，这条边的编号为4，起始顶点为2号顶点，所以把first[2]的值设为4。另外，这条“编号为4的边”是我们找到的第一条从顶点2开始的边，所以把next[4]的值设为-1。读入第5条边（137），将这条边的信息存入u[5]、v[5]和w[5]中，这条边的编号为5，起始顶点为1号顶点.此时需要将first[1]的值设置为5，将next[5]的值改为3。此时，如果我们要遍历顶点1的每条边，就很简单了。顶点1的一条边的编号存储在first[1]中。剩下的边可以通过下一个数组找到。请看下图。细心的同学会发现，此时遍历某个顶点边时的遍历顺序与阅读时的顺序正好相反。因为在为每个顶点插入一条边时，是直接插入“链表”的头部，而不是尾部。但这不会产生任何问题，这就是这种方法的美妙之处。创建邻接表的代码如下。国际,米,我;//u,v,w的数组大小要根据实际情况设置，比m的最大值大1intu[6],v[6],w[6];//first和next的数组大小要根据实际情况设置，比n的最大值大1intfirst[5],next[5];scanf("%d%d",&n,&m);//将第一个数组下标1~n的值初始化为-1，表示顶点1~n暂无边for(i=1;i<=n;i++)first[i]=-1;for(i=1;i<=m;i++){scanf("%d%d%d",&u[i],&v[i],&w[i]);//读取每条边//下面两个句子都是keyLanext[i]=first[u[i]];首先[u[i]]=i；}接下来如何遍历每一边？我们之前说过，第一个数组实际上存储的是每个顶点i（i从1到n）的第一条边。例如，顶点1的第一条边是编号为5（137）的边，顶点2的第一条边是编号为4（246）的边，顶点3没有出边。顶点4的第一条边是编号为2(246)的边。那么如何遍历顶点1的每条边呢？这也很简单。请看下图：遍历顶点1所有边的代码如下。k=first[1];//第1个顶点的一条边的个数（实际上是***读取的边）while(k!=-1)//其余的边可以在依次下一个数组{printf("%d%d%d\n",u[k],v[k],w[k]);k=下一个[k]；}遍历每个顶点的所有边的代码如下。对于（i=1；i<=n；i++）{k=first[i]；while(k!=-1){printf("%d%d%d\n",u[k],v[k],w[k]);k=下一个[k]；可以发现，使用邻接表存储图的时间和空间复杂度是O(M)，遍历每条边的时间复杂度也是O(M)。如果图是稀疏图，则M远小于N2。因此，用邻接表来存储稀疏图要比用邻接矩阵来存储要好得多。原文链接：http://ahalei.blog.51cto.com/4767671/1391988
