Question

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

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

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

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

图7-4-2

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

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

有了这个矩阵，我们就可以很容易地知道图中的信息。
1.我们要判定任意两顶点是否有边无边就非常容易了。
2.我们要知道某个顶点的度，其实就是这个顶点v_i在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v₁的度就是1+0+1+0=2。
3.求顶点v_i的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

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

图7-4-3

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

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

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

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

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

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

图7-4-4

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

/* 顶点类型应由用户定义 */
typedef char VertexType;             
/* 边上的权值类型应由用户定义 */
typedef int EdgeType;                
/* 最大顶点数，应由用户定义 */
#define MAXVEX 100                   
/* 用65535来代表∞ */
#define INFINITY 65535               
typedef struct
{
    /* 顶点表 */
    VertexType vexs[MAXVEX];         
    /* 邻接矩阵，可看作边表 */
    EdgeType arc[MAXVEX][MAXVEX];    
    /* 图中当前的顶点数和边数 */
    int numVertexes, numEdges;       
} MGraph;

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

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    /* 输入顶点数和边数 */
    scanf("%d,%d", &G->numVertexes, &G->numEdges);    
    /* 读入顶点信息，建立顶点表 */
    for (i = 0; i < G->numVertexes; i++)              
        scanf(&G->vexs[i]);
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j <G->numVertexes; j++)
            /* 邻接矩阵初始化 */
            G->arc[i][j] = INFINITY;                  
    /* 读入numEdges条边，建立邻接矩阵 */
    for (k = 0; k < G->numEdges; k++)                 
    {
        printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
        /* 输入边(vi,vj)上的权w */
        scanf("%d,%d,%d", &i, &j, &w);                
        G->arc[i][j] = w;
        /* 因为是无向图，矩阵对称 */
        G->arc[j][i] = G->arc[i][j];                  
    }
}

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