7.4.1　邻接矩阵

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。于是我们的邻接矩阵的方案就诞生了。

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

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

7.4.1　邻接矩阵 - 图1

我们来看一个实例，图7-4-2的左图就是一个无向图。

7.4.1　邻接矩阵 - 图2

图7-4-2

我们可以设置两个数组，顶点数组为ver-tex[4]={v0,v1,v2,v3}，边数组arc[4][4]为图7-4-2右图这样的一个矩阵。简单解释一下，对于矩阵的主对角线的值，即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3]，全为0是因为不存在顶点到自身的边，比如v0到v0。arc[0][1]=1是因为v0到v1的边存在，而arc[1][3]=0是因为v1到v3的边不存在。并且由于是无向图，v1到v3的边不存在，意味着v3到v1的边也不存在。所以无向图的边数组是一个对称矩阵。

嗯？对称矩阵是什么？忘记了不要紧，复习一下。所谓对称矩阵就是n阶矩阵的元满足aij=aji，（0≤i,j≤n）。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

有了这个矩阵，我们就可以很容易地知道图中的信息。

1.我们要判定任意两顶点是否有边无边就非常容易了。

2.我们要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v1的度就是1+0+1+0=2。

3.求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

我们再来看一个有向图样例，如图7-4-3所示的左图。

7.4.1　邻接矩阵 - 图3

图7-4-3

顶点数组为vertex[4]={v0,v1,v2,v3}，弧数组arc[4][4]为图7-4-3右图这样的一个矩阵。主对角线上数值依然为0。但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到arc[1][0]=1，而v0到v1没有弧，因此arc[0][1]=0。

有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。

与无向图同样的办法，判断顶点vi到vj是否存在弧，只需要查找矩阵中arc[i][j]是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找arc[i][j]为1的顶点。

在图的术语中，我们提到了网的概念，也就是每条边上带有权的图叫做网。那么这些权值就需要存下来，如何处理这个矩阵来适应这个需求呢？我们有办法。

设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

这里wij表示（vi,vj）或<vi,vj>上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。有同学会问，为什么不是0呢？原因在于权值wij大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。如图7-4-4左图就是一个有向网图，右图就是它的邻接矩阵。

7.4.1　邻接矩阵 - 图4

图7-4-4

那么邻接矩阵是如何实现图的创建的呢？我们先来看看图的邻接矩阵存储的结构，代码如下。

  1. /* 顶点类型应由用户定义 */
  2. typedef char VertexType;             
  3. /* 边上的权值类型应由用户定义 */
  4. typedef int EdgeType;                
  5. /* 最大顶点数，应由用户定义 */
  6. #define MAXVEX 100                   
  7. /* 用65535来代表∞ */
  8. #define INFINITY 65535               
  9. typedef struct
  10. {
  11.     /* 顶点表 */
  12.     VertexType vexs[MAXVEX];         
  13.     /* 邻接矩阵，可看作边表 */
  14.     EdgeType arc[MAXVEX][MAXVEX];    
  15.     /* 图中当前的顶点数和边数 */
  16.     int numVertexes, numEdges;       
  17. } MGraph;

有了这个结构定义，我们构造一个图，其实就是给顶点表和边表输入数据的过程。我们来看看无向网图的创建代码。

  1. /* 建立无向网图的邻接矩阵表示 */
  2. void CreateMGraph(MGraph *G)
  3. {
  4.     int i, j, k, w;
  5.     printf("输入顶点数和边数:\n");
  6.     /* 输入顶点数和边数 */
  7.     scanf("%d,%d", &G->numVertexes, &G->numEdges);    
  8.     /* 读入顶点信息，建立顶点表 */
  9.     for (i = 0; i < G->numVertexes; i++)              
  10.         scanf(&G->vexs[i]);
  11.     for (i = 0; i < G->numVertexes; i++)
  12.         for (j = 0; j <G->numVertexes; j++)
  13.             /* 邻接矩阵初始化 */
  14.             G->arc[i][j] = INFINITY;                  
  15.     /* 读入numEdges条边，建立邻接矩阵 */
  16.     for (k = 0; k < G->numEdges; k++)                 
  17.     {
  18.         printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
  19.         /* 输入边(vi,vj)上的权w */
  20.         scanf("%d,%d,%d", &i, &j, &w);                
  21.         G->arc[i][j] = w;
  22.         /* 因为是无向图，矩阵对称 */
  23.         G->arc[j][i] = G->arc[i][j];                  
  24.     }
  25. }

从代码中也可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n+n2+e)，其中对邻接矩阵G.arc的初始化耗费了O(n2)的时间。