邻接矩阵是表示顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，顶点序号依次为0，1，…，n-1，则G的邻接矩阵是具有如下定义的n阶方阵A：

A[i][j]=1表示顶点i与顶点j邻接，即i与j之间存在边或者弧。

A[i][j]=0表示顶点i与顶点j不邻接（0≤i，j≤n-1）。

邻接矩阵是图的顺序存储结构，由邻接矩阵的行数或列数可知图中的顶点数。对于无向图，邻接矩阵是对称的，矩阵中“1”的个数为图中总边数的两倍，矩阵中第i行或第i列的元素之和即为顶点i的度。对于有向图，矩阵中“1”的个数为图的边数，矩阵中第i行的元素之和即为顶点i的出度，第j列元素之和即为顶点j的入度。

如图7-4a所示，顶点4的出度为1，入度为2，反映到其对应的邻接矩阵中，i=4这一行中有1个“1”，j=4这一列中有两个“1”。

图7-4b所示是有向有权图，即图的边都是有权重的，反映到其对应的邻接矩阵中，不再像无权图那样，矩阵中只有“0”和“1”代表两顶点之间有无边存在，而是有边存在，则无权图中的“1”改为边的权值；若无边存在，则无权图中的“0”改为“∞”（在具体的程序中，“∞”用一个比图中所有权值还要大的数来表示）。

图7-4 图用邻接矩阵存储

a）无权图 b）有权图

说明：对于有权图的存储，不同的书对某顶点到其自身的路径长度有不同的规定，有的规定为0，表示自己到自己距离为0；有的规定为无穷大，表示自己到自己没有路径。本书采用第一种规定。(www.daowen.com)

邻接矩阵的结构型定义如下：

说明：邻接矩阵的定义在考研中的用法分为以下两种情况。

1）如果题目明确说明图采用邻接矩阵表示，并且要求写出邻接矩阵的定义，则需要将上述代码全部写出。

2）如果题目没有要求写出邻接矩阵的定义，只是说图采用邻接矩阵表示，此时不需要写出以上代码。但是要记住以上代码，因为在解题中要引用结构体的各成员，下面以一个函数为例说明其用法。

函数f（）的参数是一个表示图的结构体变量G，要记住G的各个成员名称，以便在题目中对其进行引用。例如，若要取图的顶点数赋值给a，就可以直接写成a=G.n；若要检测一下编号为i的顶点和编号为j的顶点是否邻接，则看G.edges[i][j]是否等于1。