5.2 图的顺序存储

5.2.1 邻接矩阵

将图用数组存储，图中顶点的信息保存在一个一维数组中，而图中各顶点之间的关系则保存在一个二维数组中，这个二维数组称为邻接矩阵。所谓邻接矩阵，是指以矩阵这种形式保存顶点之间的邻接关系。

1. 有向图的邻接矩阵

假设有向图 ​ G=(V, E) 具有 ​ n 个顶点，即 ​ V = \{v_0, v_1, \dots, v_{n-1}\} 。其邻接矩阵的存储可以用一个 ​ n \times n 的方形矩阵表示。假设该矩阵的名称为 ​ A ，​ A 中 ​ i 行 ​ j 列的元素为 ​ A[i][j] ，那么当 ​ \langle v_i, v_j \rangle 是该有向图中的一条弧时，​ A[i][j] = 1 ，否则 ​ A[i][j] = 0 。例如有向图 ​ G_1 的邻接矩阵如下：

从邻接矩阵中可以发现，有向图 ​ G_1 中顶点 ​ v_i 的出度是邻接矩阵第 ​ i 行元素中值为 “1” 的个数，而 ​ v_i 的入度是邻接矩阵第 ​ i 列元素中值为 “1” 的个数，而 ​ v_i 的度即为第 ​ i 行元素中值为 “1” 的个数与第 ​ i 列元素中值为 “1” 的个数之和。而且有向图 ​ G_1 中弧的数目等于邻接矩阵中 “1” 的个数。

2. 无向图的邻接矩阵

对于 ​ n 个顶点的无向图也可以用 ​ n \times n 的邻接矩阵表示。同样假设该矩阵为 ​ A ，​ A 中 ​ i 行 ​ j 列的元素为 ​ A[i][j] ，那么当 ​ (v_i, v_j) 是该无向图中的一条边时，​ A[i][j] = 1 ；否则 ​ A[i][j] = 0 。例如无向图 ​ G_2 的邻接矩阵如下：

观察该邻接矩阵可知，第 ​ i 个顶点的度为邻接矩阵中第 ​ i 行中 “1” 的个数或第 ​ i 列中 “1” 的个数，这与有向图的邻接矩阵不同。还可发现，该邻接矩阵是一个对称矩阵，这是因为图中的每条边在邻接矩阵中被描述了两次，因此图中边的数目等于邻接矩阵中 “1” 的个数的一半。

3. 有向网和无向网的邻接矩阵

对于含有权值的有向网或无向网，同样可以使用邻接矩阵来表示。如果网中两个顶点之间存在弧或边，则其对应的邻接矩阵元素值为弧或边上的权值；如果网中两个顶点之间不存在弧或边，则其对应的邻接矩阵元素值为 ​ \infty ，这里 ​ \infty 只是一个标记符合，表示一个计算机允许的、大于所有权值的数，它的具体值取决于实际应用。例如，图 5.7 (a) 描述的是旅游城市地理位置之间的路线，可以使用一个无向网来表示。其邻接矩阵如图 5.7 (b) 所示。

5.2.2 图的顺序存储实现

图的邻接矩阵是一种采用二维数组表示顶点之间相邻关系的存储结构。

邻接矩阵类型声明如下：

#define MAXV <最大顶点个数>
#define INF 32767          //定义无穷大
typedef struct
{
    int no ;              //顶点的编号
    OtherInfo info;       //顶点的其他信息
}VertexType ;            //顶点的类型
typedef struct
{
    int edges[MAXV][MAXV]; //邻接矩阵数组
    int n,e;              //顶点数,边数
    VertexType vexs[MAXV]; //存放顶点信息
}MGraph ;

仔细观察邻接矩阵有如下特点：

一个图的邻接矩阵表示是唯一的。

邻接矩阵的存储空间为 ​ O(n^2) ，非常适合稠密图。

对于无向图，邻接矩阵数组的第 ​ i 行（或第 ​ i 列）非零元素、非 ​ \infty 元素的个数正好是顶点 ​ i 的度。

对于有向图，邻接矩阵数组的第 ​ i 行（或第 ​ i 列）非零元素、非 ​ \infty 元素的个数正好是顶点 ​ i 的出度（或入度）。