一、基本定义

图的邻接矩阵存储由两部分组成：

  • 一个一维数组，用于存放顶点；
  • 一个二维数组，用于表示顶点之间的邻接关系。

设图为 G=(V,E)G=(V,E)，共有 nn 个顶点：

V={v1,v2,…,vn}V=\{v_1,v_2,\ldots,v_n\}

其邻接矩阵记为 A=(aij)n×nA=(a_{ij})_{n\times n}。在无权图中：

aij={1,vi 与 vj 之间有边0,vi 与 vj 之间无边a_{ij}= \begin{cases} 1, & v_i\text{ 与 }v_j\text{ 之间有边}\\ 0, & v_i\text{ 与 }v_j\text{ 之间无边} \end{cases}

在程序中，aija_{ij} 对应数组元素 A[i][j]。

核心： 邻接矩阵就是用一个 n×nn\times n 的矩阵记录任意两个顶点之间是否有边。

二、不同类型图的邻接矩阵

1. 有向图

在有向图中，aij=1a_{ij}=1 表示存在从 viv_i 指向 vjv_j 的有向边：

vi→vjv_i\to v_j

因此，矩阵中的行表示起点，列表示终点。

例如：

A=[011001100]A= \begin{bmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{bmatrix}

第一行 [0,1,1][0,1,1] 表示 v1→v2v_1\to v_2 和 v1→v3v_1\to v_3。

2. 无向图

无向图中，若 viv_i 与 vjv_j 相邻，则必有 aij=ajia_{ij}=a_{ji}。所以无向图的邻接矩阵是对称矩阵：

A=AT\boxed{A=A^T}

同一条无向边会在矩阵中记录两次。因此，可以只存储上三角或下三角部分，但空间复杂度仍为 O(n2)O(n^2)。

3. 带权图（网）

带权图中，矩阵元素记录边的权值。在最短路径等问题中，通常规定：

aij={wij,vi 与 vj 之间有边∞,vi 与 vj 之间无边a_{ij}= \begin{cases} w_{ij}, & v_i\text{ 与 }v_j\text{ 之间有边}\\ \infty, & v_i\text{ 与 }v_j\text{ 之间无边} \end{cases}

通常还规定主对角线元素为 00。例如：

A=[03∞305∞50]A= \begin{bmatrix} 0 & 3 & \infty\\ 3 & 0 & 5\\ \infty & 5 & 0 \end{bmatrix}

这表示边 (v1,v2)(v_1,v_2) 的权值为 33，边 (v2,v3)(v_2,v_3) 的权值为 55，而 v1v_1 与 v3v_3 之间无边。

当然是0是还是♾️都无所谓，看题目要求

三、存储结构

邻接矩阵常见的 C 语言存储结构如下：

typedef struct {
    VertexType vex[MAXV];
    int edge[MAXV][MAXV];
    int vexnum;
    int arcnum;
} MGraph;
成员 含义
vex 存储顶点信息
edge 存储边或弧的信息
vexnum 图的顶点数
arcnum 图的边数或弧数

四、常见性质与计算

以下结论默认讨论不含自环的简单无权图。

1. 无向图顶点的度

无向图中，顶点 viv_i 的度等于第 ii 行元素之和，也等于该行非零元素的个数：

D(vi)=∑j=1naij\boxed{D(v_i)=\sum_{j=1}^{n}a_{ij}}

例如：

A=[0110101111000100]A= \begin{bmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 \end{bmatrix}

第二行有三个 11，因此 D(v2)=3D(v_2)=3。

2. 有向图顶点的度

有向图中：

  • 第 ii 行元素之和是顶点 viv_i 的出度；
  • 第 ii 列元素之和是顶点 viv_i 的入度。
OD(vi)=∑j=1naij,ID(vi)=∑j=1naji\boxed{OD(v_i)=\sum_{j=1}^{n}a_{ij}},\qquad \boxed{ID(v_i)=\sum_{j=1}^{n}a_{ji}}

顶点的总度数为：

TD(vi)=OD(vi)+ID(vi)\boxed{TD(v_i)=OD(v_i)+ID(v_i)}

重点： 行看出度，列看入度。

3. 图的边数

无向图中，每条边在矩阵中出现两次，因此：

∣E∣=12∑i=1n∑j=1naij\boxed{|E|=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}}

有向图中，每条弧只出现一次，因此：

∣E∣=∑i=1n∑j=1naij\boxed{|E|=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}}

五、复杂度与适用场景

操作 时间或空间复杂度
存储邻接矩阵 O(n2)O(n^2)
判断两顶点之间是否有边 O(1)O(1)
添加或删除一条边 O(1)O(1)
查找一个顶点的所有邻接点 O(n)O(n)
使用邻接矩阵进行 DFS 或 BFS O(n2)O(n^2)

邻接矩阵的空间复杂度只与顶点数 nn 有关，与实际边数无关。因此：

  • 稠密图中边数较多，邻接矩阵结构简单且查询效率高，较为适用；
  • 稀疏图中大量位置为 00，容易浪费空间，通常更适合邻接表。

作为对比，邻接表进行 DFS 或 BFS 的时间复杂度为 O(n+∣E∣)O(n+|E|)。

六、邻接矩阵的幂

设 AA 为图的邻接矩阵，则矩阵幂中的元素 (Ak)ij(A^k)_{ij} 表示：

从顶点 vi 到 vj、长度为 k 的游走数量\boxed{\text{从顶点 }v_i\text{ 到 }v_j\text{、长度为 }k\text{ 的游走数量}}

矩阵A是有向图G的邻接矩阵，若矩阵A²的某元素(a2)ij=3(a^2)_{ij}=3，则说明

从顶点 i 到 j 存在 3 条长度为 2 的路径

看网课说比较重要，是往年真题考过的偏门知识点

七、速记

考点 结论
存储结构 顶点数组 + n×nn\times n 矩阵
无向图 A=ATA=A^T
无向图顶点度 第 ii 行元素之和
有向图出度 第 ii 行元素之和
有向图入度 第 ii 列元素之和
无向图边数 矩阵中所有 11 的个数除以 22
有向图弧数 矩阵中所有 11 的个数
查询一条边 O(1)O(1)
查找全部邻接点 O(n)O(n)
DFS、BFS O(n2)O(n^2)
(Ak)ij(A^k)_{ij} 从 viv_i 到 vjv_j 的长度为 kk 的游走数量

记忆： 无向看对称，有向行出列入；查询一条边是 O(1)O(1)，遍历邻接点是 O(n)O(n)。

接下来又要不更新一段时间了，我要开始勇闯二叉树和邻接矩阵的算法题部分，写代码去了。
现在数学的第一章节的练习题已经做完3/4了，到时候继续美美开第二章。
不过这有点太慢了，要不要考虑顺手把计算机组成原理也开了呢，大概了解下概念？

甘小妹