7.2.2　邻接表

图的邻接矩阵表示法虽然有其自身的优点，但对于点比较多，边很少的稀疏图来讲，用邻接矩阵方法会造成存储空间的极大浪费。如图7－14所示，我们要将此图用邻接矩阵法存储，可以看到，只有一条弧存在，没有其他弧，这些空间全部都浪费了。

图7－14的稀疏图用邻接表来存储，如图7－15所示，可以看到节省了大量的空间，下面我们来研究一下图用邻接表是如何存储的。

图7－14 稀疏图邻接矩阵存储

图7－15 图邻接表存储

图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成，如图7－16所示，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。表结点存放的是邻接顶点在数组中的索引。图7－17所示对于无向图邻接表存储，表结点有几个，该表头结点的度就是几个。例如图7－17中，结点A的度为后面链接的结点个数，是3。使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

图7－16 邻接表结构

有向图的邻接表有邻接表和逆邻接表之分。邻接表的表结点存放的是从表头结点出发的有向边所指的尾顶点；逆邻接表的表结点存放的则是指向表头结点的某个头顶点。如图7－18所示，图7－18（b）和图7－18（c）分别为有向图7－18（a）的邻接表和逆邻接表。可以很清楚地看到，在邻接表中找某一个结点的出度非常容易，如图7－18（b）中结点A的出度即为2，结点B的出度是1；逆邻接表中求某个结点的入度非常容易，如图7－18（c）中结点A的入度是1，结点C的入度是2。

图7－17 无向图及其邻接表

图7－18 有向图邻接表和逆邻接表

以上所讨论的邻接表所表示的都是不带权的图，如果要表示带权图，可以在表结点中增加一个存放权的字段，其效果如图7－19所示。

图7－19 带权图邻接表

注意：观察图7－19可以发现，删除存储表头结点的数组中的某一元素，有可能使部分表头结点索引号改变，从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题。在实际创建邻接表时，甚至可以使用链表代替数组存放表头结点或使用顺序表代替链表存放表结点。对所学的数据结构知识应当根据实际情况及所使用语言的特点灵活应用，切不可生搬硬套。

邻接表存储结构的形式化说明如下。

算法7.2 邻接表存储

对于有n个顶点、e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。很显然在边很稀疏（即e远小于n（n－1）／2时）的情况下，用邻接表存储所需的空间要比邻接矩阵所需的n（n－1）／2要节省得多。

此外，在无向图的邻接表中，顶点vi的度恰好就是第i个单链表上结点的个数。而在有向图中，第i个单链表上结点的个数只是顶点vi的出度，要想求得该顶点的入度，则必须遍历整个邻接表。在所有单链表中查找邻接点域的值为i的结点并计数求和。由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，它需要扫描整个邻接表才能得到结果。对此，我们可以对每一顶点vi建立一个递邻接表，即对每个顶点vi建立一个链接以顶点vi为弧头的弧的表，如图7－18所示。这样求顶点vi的入度即是逆邻接表中第i行结点个数。

在邻接表上，我们很容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需要搜索第i个或第j个链表，这比起邻接矩阵法（通过判断A［i，j］实现），不及邻接矩阵法方便。