图有两种存储方式，邻接矩阵和邻接表。

邻接矩阵

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

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

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
 

从这个矩阵中，很容易知道图中的信息。

（1）要判断任意两顶点是否有边无边就很容易了；
（2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；
（3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；

而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。
若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为

小结

1、在简单应用中，可以直接用二维数组作为图的邻结矩阵，如int G[105][105]。

2、无向图的邻结矩阵是对称矩阵，对规模很大的邻结矩阵可采用压缩存储。

3、邻结矩阵表示法的空间复杂度为O(n²)，其中n为图的顶点数|V|。

4、用邻结矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。

5、稠密图适合使用邻结矩阵的存储表示。

6、设图G的邻结矩阵为A，Aⁿ的元素Aⁿ[i][j]等于由顶点i到顶点j的长度为n的路径的数目。

课后习题

【2013年真题】设图的邻接矩阵 A 如下所示。各顶点的度依次是（）

A. 1，2，1，2         B. 2，2，1，1 
C. 3，4，2，3         D. 4，4，2，2

参考答案：C
答案解析：各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。 

【2015年真题】已知含有 5 个顶点的图 G 如下图所示。

请回答下列问题： 
1）写出图 G 的邻接矩阵 A（行、列下标从 0 开始）。 
2）求 A2，矩阵 A2中位于 0 行 3 列元素值的含义是什么？ 
3）若已知具有 n（n≥2）个顶点的图的邻接矩阵为 B，则 Bm（2≤m≤n）中非零元素的含义是什 
么？

参考答案：
1）图 G 的邻接矩阵 A 如下： 

2）A2如下： 

0 行 3 列的元素值 3 表示从顶点 0 到顶点 3 之间长度为 2 的路径共有 3 条。 
3）Bm（2≤m≤n）中位于 i 行 j 列（0≤i，j≤n-1）的非零元素的含义是：图中从顶点 i 到顶点 j 
长度为 m 的路径条数。