图的邻接矩阵存储

基本概念

要存储一个图，必须要存储其顶点数据和顶点关系。顶点数据可以用数组存储，下标为顶点编号。对于顶点关系，我们用**邻接矩阵（Adjacency Matrix）**进行存储。邻接矩阵简单来说就是检测从列到行的顶点是否有边。

$G$ 的邻接矩阵是满足如下条件的 $n$ 阶矩阵：

• 若 $(v_i,v_j)\in E$ 或者 $(v_j,v_i)\in E$，则 $A[i][j]=1$
• 否则，$A[i][j]=0$

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。

基本操作

对于邻接矩阵，我们要判断两个顶点是否相邻，只需要判断对应数组的分量是否为 1。

在顶点不变的情况下，可以直接通过修改数组分量来添加或者删除边：

• 在有向图中，统计第 $i$ 行 $1$ 的个数可得顶点 $v_i$ 的出度，统计第 $j$ 列 $1$ 的个数可得顶点 $v_j$ 的入度。
• 在无向图中，统计第 $i$ 行（列）$1$ 的个数可得顶点 $v_i$ 的度。

带权图（网络）

对于带权的图（网络，Network），邻接矩阵中存放的便是边的权重，对于没有边的两顶点，根据权重所指存储 $0$ 或者无穷（$\infty$）。

$$A[i][j]=w_{ij}\text{若 }(v_i,v_j)\in E\text{ 或者 }(v_j,v_i)\in E/A[i][j]=0\text{ 或 }\infty \text{否则}$$

复杂度分析

邻接矩阵需要 $O(n^2)$ 的存储空间，其中 $n$ 为顶点数。对于稀疏图来说，这会造成大量空间浪费。

链接到

• 上一个知识点：7.1 图的基本概念
• 下一个知识点：7.3 图的邻接表存储