1.2 图的存储表示

上一节中对图的一些基本概念和术语进行了介绍，对图有了初步了解之后，可将实际问题抽象成图结构，若想使计算机能够处理图结构，必须要明确在计算机中如何去描述一个图。图的结构比较复杂，图的信息包括顶点和边两部分，任意两个顶点之间都有可能存在联系，顶点之间的逻辑关系也错综复杂，恰当的表示方法将有利于解决问题。图的表示方式有很多种，本节主要介绍以下四种表示方式： 邻接矩阵存储法、邻接表存储法、十字链表存储法、邻接多重表存储法 。

1.2.1 邻接矩阵存储法

由于矩阵在计算机中容易存储和处理，所以可以利用矩阵将图表示在计算机中，并且还可以利用矩阵的一些运算来描述图的一些性质，便于研究图论中的一些问题。

所谓图的邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），该二维数组称为图的 邻接矩阵 （Adjacency Matrix）。

若 G =（ V ， E ）是一个包含 n 个节点的图，则 G 的邻接矩阵 A 是满足式（1-1）的 n 阶方阵：

图1-10分别列出了无向图 G ₁ 及其邻接矩阵 A ₁ 和有向图 G ₂ 及其邻接矩阵 A ₂ 。

若 G =（ V ， E ）是一个包含 n 个节点的网，则 G 的邻接矩阵 A 是满足式（1-2）的 n 阶方阵：

其中 w _ij 表示边（ v _i ， v _j ）或弧< v _i ， v _j >上的权值。如图1-11所示为一个有向网及其邻接矩阵。

通过邻接矩阵，可以很方便地看出两个顶点之间是否有边相连。但是，如果想要确定这个图（或网）中有多少条边（或弧），则必须对整个二维数组进行遍历，所花费的时间代价很大，因此这种表示方法适合于稠密图。

1.2.2 邻接表存储法

当一个图为稀疏图时，使用邻接矩阵会浪费大量的存储空间，有没有一种表示方法可以减少这种不必要的浪费呢？接下来介绍的邻接表可以很好地解决这一问题。

邻接表 （Adjacency List）是图的一种链式存储结构。在邻接表中，对图中每个节点 v _i 建立一个单链表，第 i 个单链表中的节点表示依附于顶点 v _i 的边（对于有向图是以顶点 v _i 为尾的弧）。在邻接表中存在两种节点：表节点和头节点。如图1-12所示。

表节点由3个域组成，其中邻接点域（adjvex）指示与顶点 v _i 邻接的点在图中的位置，链域（nextarc）指向与头节点相邻接的下一条边或弧的顶点，数据域（info）存储和边或弧相关的信息。

头节点由2个域组成，其中数据域（data）存放顶点 v _i 的信息，指针域（firstarc）指向第一条邻接边。无向图 G ₁ 和有向图 G ₂ 的邻接表分别如图1-13和图1-14所示。

在无向图的邻接表中，顶点 v _i 的度恰为第 i 个链表中的节点个数，而在有向图中，第 i 个链表中的节点个数只是顶点 v _i 的出度，若求入度，则必须遍历整个链接表。在所有链表中其邻接点域的值为 i 的节点个数是顶点 v _i 的入度。

因此，为了便于确定顶点 v _i 的入度或以顶点 v _i 为头的弧，可以建立一个有向图的 逆邻接表 （Inverse Adjacency List），即对于每个顶点 v _i ，将邻接表中所有以 v _i 为弧头的弧链接起来。如图1-15所示为一个有向图及其逆邻接表。

在邻接表中，我们可以快速地找到任一顶点的第一个邻接点和下一个邻接点，但是若要判断两个顶点 v _i 和 v _j 之间是否有边或弧相连，则需要遍历第 i 个或第 j 个单链表，这一点不及邻接矩阵方便。

1.2.3 十字链表存储法

十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中的每条弧都有一个节点，对应于每个顶点也有一个节点，如图1-16所示。

弧节点由5个域组成，其中尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置，链域hlink指向弧头相同的下一条弧，链域tlink指向弧尾相同的下一条弧，info域指向该弧的相关信息。

顶点节点由3个域组成，其中data域存放与顶点相关的信息，firstin和firstout两个域分别指向以该顶点为弧头和弧尾的第一条弧。如图1-17所示为有向图 G ₅ 及其十字链表。

1.2.4 邻接多重表存储法

邻接多重表是无向图的另一种链式存储结构。在邻接表中容易求得顶点和边的各种信息。但是，在邻接表中每一条边（ v _i ， v _j ）有两个节点，分别在第 i 个和第 j 个单链表中，这给某些图的操作带来了不便。例如，求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的表节点中去遍历，效率低下。因此，在进行此类操作时，采用邻接多重表的表示方式更为合适。

邻接多重表的结构和有向图的十字链表类似。在邻接多重表中，每条边用一个节点表示，每个顶点也用一个节点表示，如图1-18所示。

表节点由6个域组成，其中标志域（mark）标记该条边是否被搜索过，ivex和jvex指示该边依附的两个顶点在图中的位置，ilink指向下一条依附于顶点ivex的边，jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。

表节点由2个域组成：data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边。如图1-19所示为无向图 G ₆ 及其邻接多重表。