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

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

    设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
    image.png
    我们来看一个实例，图7-4-2的左图就是一个无向图。
    image.png
    我们可以设置两个数组，顶点数组为ver-tex[4]={v 0 ,v 1 ,v 2 ,v 3 }，边数组arc[4][4]为图7-4-2右图这样的一个矩阵。简单解释一下，对于矩阵的主对角线的值，即arc[0][0]、arc[1][1]、arc[2][2]、arc[3][3]，全为0是因为不存在顶点到自身的边，比如v 0 到v 0 。arc[0][1]=1是因为v 0 到v 1 的边存在，而arc[1][3]=0是因为v 1 到v 3 的边不存在。并且由于是无向图，v 1 到v 3 的边不存在，意味着v 3 到v 1 的边也不存在。所以无向图的边数组是一个对称矩阵。

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

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


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

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

    与无向图同样的办法，判断顶点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 ）或上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。有同学会问，为什么不是0呢？原因在于权值w ij 大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。

    如图7-4-4左图就是一个有向网图，右图就是它的邻接矩阵。
    image.png
    那么邻接矩阵是如何实现图的创建的呢？我们先来看看图的邻接矩阵存储的结构，代码如下。

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

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

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

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