图的存储结构

邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

假设图 G＝(V，E) 有 n 个顶点，即 V＝{ v0，v1，…，vn-1 }，则邻接矩阵是一个 n×n 的方阵，定义为：

下图中两个图的邻接矩阵分别为：

使用邻街矩阵存储图
并且，此时顶点 a、b、c、d 在存储顶点的数组中所对应的下标分别为 0、1、2、3。
实际上这一表示形式也可以推广至带权图，若图 G 是网图，有 n 个顶点，则它的邻接矩阵是一个 n×n 的方阵阵，定义为：

下图给出了一个有向网图和它的邻接矩阵。

带权图及邻接矩阵
从图的邻接矩阵存储方法容易看出：首先，无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。其次，对于无向图，邻接矩阵的第 i 行（或第 i 列）非 ∞ 元素的个数正好是第 i 个顶点的度 TD(vi)。再次，对于有向图，邻接矩阵的第 i 行（第 i 列）非 ∞ 元素的个数正好是第 i 个顶点的出度 OD(vi)（入度 ID(vi)）。最后，通过邻接矩阵很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
从空间上看，不论顶点 u、v 之间是否有边，在邻接矩阵中都需预留存储空间，因为每条边所需的存储空间为常数，所以邻接矩阵需要占用 O(n2) 的空间，这一空间效率较低。具体来说，邻接矩阵的不足主要在两个方面。首先，尽管由 n 个顶点构成的图中最多可以有n2条边，但是在大多数情况下，边的数目远远达不到这个量级，因此，在邻接矩阵中大多数单元都是闲置的。其次，矩阵结构是静态的，其大小 N 需要预先估计，然后创建 N×N 的矩阵。然而，图的规模往往是动态变化的，N 的估计过大会造成更多的空间浪费，如果估计过小则经常会出现空间不够用的情况。

邻接表

邻接表（Adjacency List）是图的一种链式存储方法，邻接表表示法类似于树的孩子链表表示法。在邻接表中对于图 G 中的每个顶点 vi 建立一个单链表，将所有邻接于 vi 的顶点链成一个单链表，并在表头附设一个表头结点，这个单链表就称为顶点 vi 的邻接表。

在邻接表中共有两种结点结构，分别是边表结点和表头结点。每个边表结点由 3 个域组成，如图（a）所示。其中邻接点域（adjvex）指示与顶点 vi 邻接的顶点在图中的位置，链域（nextedge）指向下一条边所在的结点，数据域（info）存储和边有关的信息，如权值等信息。在头结点中，结构如图（b）所示，除了设有链域（firstedge）指向链表中的第一个结点之外，还有用于存储顶点 vi 相关信息的数据域（data）。

邻接表结点结构

这些表头结点（可以链接在一起）以顺序的结构形式进行存储，以便随机访问任一顶点的链表。下图给出了图的邻接表存储示例。

图的邻接表
就存储空间而言，对于 n 个顶点、m 条边的无向图，若采用邻接表作为存储结构，则需要 n 个表头结点和 2m 个边表结点。显然在边稀疏的情况下，用邻接表存储要比使用邻接矩阵节省空间。

在无向图的邻接表中，顶点 vi 的度恰为顶点 vi 的邻接表中边表结点的个数；而在有向图中，顶点 vi 的邻接表中边表结点的个数仅为顶点 vi 的出度，为求顶点 vi 的入度必须遍历整个邻接表。在所有链表中其邻接点域的值指向 vi 的位置的结点个数是顶点 vi 的入度。为了方便求得有向图中顶点的入度，可以建立一个有向图的逆邻接表，如图（e）所示。

在邻接表中容易找到一个顶点的邻接点，但是要判定两个顶点 vi 和 vj 之间是否有边，则需要搜索顶点 vi 或顶点 vj 的邻接表，与邻接矩阵相比不如邻接矩阵方便。

十字链表

十字链表(Orthogonal List)是有向图的另一种链式存储结构，是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

十字链表结点结构

◆ data 域：存储和顶点相关的信息；
◆ 指针域 firstin：指向以该顶点为弧头的第一条弧所对应的弧结点；
◆ 指针域 firstout：指向以该顶点为弧尾的第一条弧所对应的弧结点；
◆ 尾域 tailvex：指示弧尾顶点在图中的位置；
◆ 头域 headvex：指示弧头顶点在图中的位置；
◆ 指针域 headlink：指向弧头相同的下一条弧；
◆ 指针域 taillink：指向弧尾相同的下一条弧；
如果是网，还可以再增加一个 weight 域来存储权值。

有向图的十字链表结构
从这种存储结构图可以看出，从一个顶点结点的 firstout 出发，沿表结点的 taillink 指针构成了邻接表的链表结构，而从一个顶点结点的 firstin 出发，沿表结点的 headlink 指针构成了逆邻接表的链表结构。

邻接多重表

邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。邻接多重表的结构和十字链表类似，每条边用一个结点表示；邻接多重表中的顶点结点结构与邻接表中的完全相同，而表结点结构如下图所示。

邻接多重表的结点结构

1. data 域：存储和顶点相关的信息；
2. 指针域 firstedge：指向依附于该顶点的第一条边所对应的表结点；
3. ivex 和 jvex 域：分别保存该边所依附的两个顶点在图中的位置；
4. 指针域 ilink：指向下一条依附于顶点 ivex 的边；

5. 指针域 jlink：指向下一条依附于顶点 jvex 的边。

   
   无向图及其多重邻接链表
   

   邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了。

边集数组

边集数组是由两个一维数组构成。一个是存储顶点信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。

边数组结构