巧妙的邻接表（数组实现）

原文地址：http://ahalei.blog.51cto.com/4767671/1391988

我们之前介绍过图中的相邻矩阵存储方法。它的空间和时间复杂性是N2。现在我将介绍另一种存储图的方法：相邻表，使空间和时间复杂性为M。对于稀疏图，M远小于N2。首先，数据如下。

4 5                1 4 9                4 3 8                1 2 5                2 4 6                1 3 7

第一行有两个整数nm。n表示顶点数(顶点数为1~n），m表示边的条数。接下来，m行表示每行有三个数x y z，表示顶点x到顶点y的边缘权值为z。下图是使用链表实现邻接表的一种方法。

上述实现方法为图中的每个顶点(左部分)建立了单链表(右部分)。这样，我们就可以通过遍历每个顶点的链表来获得顶点的所有边缘。对于讨厌指针的朋友来说，使用链表来实现邻接表简直是噩梦。在这里，我将介绍另一种使用数组实现的邻接表，这是一种在实际应用中非常容易实现的方法。这种方法是每个顶点i(i从1~n）它还保存了一个类似于“链表”的东西，它保存了从顶点i开始的所有边缘，具体如下。

首先，我们按照读入的顺序编号每个边(1~m）。比如第一条边“1” 4 9号为1，“1” 3 这一边的编号是5。

这里用u、v和w三个数组用于记录每个侧面的具体信息，即u[i]、v[i]和w[i]表示从第uu条边表示第i条[i]号顶点到v[i]号顶点（u[i]àv[i]），且权值为w[i]。

然后用first数组存储每个顶点一侧的编号。以便我们将来枚举每个顶点的所有边缘(你可能会问:只需存储其中一个边缘的编号即可？不可能，每个顶点都需要存储其所有边缘的编号！别担心，继续往下看)。例如，1号顶点有一个边缘 “1 4 9”(该条边的编号为1)，然后将first[1]的值设置为1。如果一个顶点i没有以这个顶点为起点的边缘，那么firstt[i]的值设为-1。现在我们来看看具体怎么操作，初始状态如下。

嗯？为什么上图中有一个next数组？它有什么作用？别担心，以后再解释。现在先读第一个边“1” 4 9”。

读第一条边(1) 4 9)将此侧的信息存储到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]nexttt是起点的第一个边，将是next[i]值设为-1(这个next数组似乎很神秘⊙_⊙）。

读第二条边(4) 3 8)将此侧的信息存储到u[2]、v在[2]和w[2]中，这个边的编号为2。这个边的起点是4号的顶点，所以first[4]的值设置为2。此外，这个“编号为2的边”是我们发现4号顶点的第一个边，所以next[2]的值设置为-1。

读第三条边(1) 2 5)将此侧的信息存储到u[3]、v在[3]和w[3]中，这一边的编号为3，起点为1号顶点。我们发现1号顶点已经有一个“1号边”了。如果此时first[1]的值设置为3，那么“1号边”不会丢失吗？这个时候我有办法把next[3]的值设置为1。现在你知道next数组是用来做什么的了。next[i]“前一边”的编号存储在“编号为i的边缘”中。

读第四条边(2) 4 6)将此侧的信息存储到u[4]、v在[4]和w[4]中，这一边的编号为4，起点为2，因此first[2]的值设置为4。此外，这个“4号边”是我们发现2号顶点的第一个边，所以next[4]的值设置为-1。

读第五条边(1) 3 7)将此侧的信息存储到u[5]、v在[5]和w[5]中，这一边的编号为5，起始顶点为1。此时，需要将first[1]的值设置为5，并将next[5]的值改为3。

在这个时候，如果我们想遍历1号顶点的每一个边缘，那就很简单了。1号顶点的一个边缘的编号存储在first[1]中。其余的边缘可以通过next数组找到。请参见下图。

细心的学生会发现，当遍历边的某个顶点边缘时，遍历的顺序与阅读时的顺序正好相反。因为在插入每个顶点的边缘时，直接插入“链表”的第一部分，而不是尾部。但这不会有任何问题，这就是这种方法的优点。

创建邻接表的代码如下。

int         n,m,i;                //u、v和w的数组大小应根据实际情况设置，比m的最大值大1                int         u[6],v[6],w[6];                //first和next的数组大小应根据实际情况设置，大于n的最大值                int         first[5],next[5];                scanf        (        "%d %d"        ,&n,&m);                ///初始化first数组下标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]);        ///读入每个边                        ///下面两句是关键。                        next[i]=first[u[i]];                        first[u[i]]=i;                }

接下来，如何遍历每一条边？我们之前说过，其实first数组存储的是每个顶点i(i从1~n）第一条边。例如，1号顶点的第一个边是编号为5的边(1 3 7)，2号顶点的第一边是编号为4的边(2 4 6)，3号顶点没有出向边，4号顶点的第一个边是编号为2的边(2) 4 6）。那么如何遍历1号顶点的每一边呢？也很简单。请看下图：

遍历1号顶点所有边的代码如下。

k=first[1];        // 1号顶点其中一个边的编号(其实也是最后一个读入边)                while        (k!=-1)         ///其他边缘可以在next数组中依次找到                {                        printf        (        "%d %d %d\n"        ,u[k],v[k],w[k]);                        k=next[k];                }

遍历每个顶点的所有边的代码如下。

for        (i=1;i<=n;i++)                {                        k=first[i];                        while        (k!=-1)                        {                        printf        (        "%d %d %d\n"        ,u[k],v[k],w[k]);                        k=next[k];                        }                }

可以发现，使用邻接表存储图纸的时间和空间复杂性是O(M)，时间复杂度遍历每一边也是O(M)。如果一张图是稀疏图，M远小于N2。因此，用邻接表存储稀疏图比用邻接矩阵存储好得多。