图

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

假设图 G＝(V，E) 有 n 个顶点，即 V＝{ v0，v1，…，vn-1 }，则邻接矩阵是一个 n×n 的方阵，定义为：
arc[i][j]={1∞<u，v>或(u，v)∈E反之 arc[i][j]=\begin{cases}1& \text{<u，v>或(u，v)∈E}\\infty& \text{反之}\end{cases}
arc[i][j]={
1
∞
​

<u，v>或(u，v)∈E
反之
​

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

并且，此时顶点 a、b、c、d 在存储顶点的数组中所对应的下标分别为 0、1、2、3。
实际上这一表示形式也可以推广至带权图，若图 G 是网图，有 n 个顶点，则它的邻接矩阵是一个 n×n 的方阵阵，定义为：
arc[i][j]={Wij∞<u，v>或(u，v)∈E反之 arc[i][j]=\begin{cases}W_{ij}& \text{<u，v>或(u，v)∈E}\\infty& \text{反之}\end{cases}
arc[i][j]={
W
ij
​

∞
​

<u，v>或(u，v)∈E
反之
​

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

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

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

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