数据结构第 6 章：图

408 数据结构「图」复习：核心知识点、真题题型、通用解法与易错点。

本章按照本站资料体系整理。需要说明：**408 模拟题页面把“图”列为数据结构第 6 章；408 真题页面因为没有单独把“串”列为一章，所以“图”显示为第 5 章。实际知识内容完全对应。**本站也明确建议研究考研题型时采用“知识点 → 真题 → 总结命题方式 → 模拟题补充”的顺序。(Any Docs)

这一章可以压缩成一张主线：

图的概念 → 图的存储 → BFS/DFS → 最小生成树 → 最短路径 → 拓扑排序 → 关键路径 → 图算法设计

其中真正的 408 重头戏是后四项，而且近年的算法大题非常喜欢从“邻接矩阵 + 图的某个性质”出题，例如 2021 年 EL 路径、2023 年 K 顶点、2024 年唯一拓扑序列。(Any Docs)

一、图的基本概念

这一部分单独看不难，但经常成为后面 MST、拓扑、遍历题的判断依据。

1. 顶点数、边数、度数

无向图最重要的公式：

v \in V \sum d (v) = 2∣ E ∣

这就是握手定理。

因此立即推出：

所有顶点度数之和一定为偶数；
奇数度顶点个数一定为偶数。

有向图则是：

v \in V \sum d^{+} (v) = ∣ E ∣

v \in V \sum d^{-} (v) = ∣ E ∣

所以

\sum d^{+} (v) = \sum d^{-} (v)

其中：

$d^{+} (v)$ ：出度；
$d^{-} (v)$ ：入度；
总度 $d (v) = d^{+} (v) + d^{-} (v)$ 。

题型 1：利用握手定理反推顶点数

408 真题 2017

题目大意：

一个无向图有 16 条边，其中：

度为 4 的顶点有 3 个；
度为 3 的顶点有 4 个；
其他顶点度数均小于 3；

问图至少有多少个顶点。

网站答案：11。(Any Docs)

解法

总度数：

2∣ E ∣ = 2 \times 16 = 32

已知顶点贡献：

3 \times 4 + 4 \times 3 = 24

还剩：

32 - 24 = 8

剩余顶点每个度最多为 2。

为了让顶点数最少，就应该让每个剩余顶点的度尽可能大，即都取 2。

所以至少还需要：

\frac{8}{2} = 4

因此：

3 + 4 + 4 = 11

这类题的统一套路

看到：

“至少有多少顶点”

马上想到：

要让顶点数量最少，就让未知顶点每个尽可能贡献最大的度。

反过来，如果问“最多可能多少顶点”，思路往往相反。

二、连通性与边数极值

这是图论选择题非常高频的一类。

对于 $n$ 个顶点的无向连通图：

∣ E ∣ \geq n - 1

取等号时就是树。

而简单无向图最多有：

\frac{n ( n - 1 )}{2}

条边。

题型 2：多少条边“一定连通”

408 真题 2010

题目：

一个有 7 个顶点的无向图，要保证无论这些边怎么分布，图一定连通，最少需要多少条边？

答案是 16。(docs.any1.tech)

很多人第一反应：

7 - 1 = 6

错。

$n - 1$ 的意思只是：

一个已经连通的图，至少需要 $n - 1$ 条边。

并不意味着“任意放 $n - 1$ 条边都连通”。

正确思路：先找“不连通最多能有多少边”

为了让图仍然不连通，同时让边尽可能多：

$n - 1$ 个顶点组成完全图；
留 1 个孤立顶点。

因此：

E_{m a x, 不连通} = (2 n - 1)

所以要保证连通：

∣ E ∣ \geq (2 n - 1) + 1

本题：

(2 6) + 1 = 15 + 1 = 16

必记结论

$n$ 个顶点的简单无向图，要保证一定连通：

∣ E ∣ \geq \frac{( n - 1 ) ( n - 2 )}{2} + 1

模拟题变式

网站的王道模拟题还问：

一个有 36 条边的非连通简单无向图，顶点数至少是多少？

思路完全相反：

(2 n - 1) \geq 36

得到最小 $n = 10$ 。(Any Docs)

所以“保证连通”和“已知不连通求最少顶点”本质上是一类极值问题。

三、强连通分量

有向图里：

$u \to v$ 可达，不代表 $v \to u$ ；
若任意两个顶点相互可达，则图强连通。

强连通分量是极大强连通子图。

一个很重要的结论：

把每个强连通分量缩成一个顶点，所得图一定是 DAG。

模拟题：加入一条边对强连通分量数的影响

网站“竟成·模拟三”考：

两个不同强连通分量之间原来存在从 $C_{1}$ 到 $C_{2}$ 的路径，再增加一条适当的反向边，强连通分量数量可能怎样变化？

答案：可能减少。(Any Docs)

因为原来：

C_{1} \to \dots \to C_{2}

如果新增：

C_{2} \to C_{1}

就可能形成环，于是这些分量合并成一个更大的强连通分量。

高频判断

加边只能增加可达性，所以：

连通分量数不会增加；
强连通分量数也不会增加；
可能不变；
可能减少。

删除边则反过来。

四、图的存储结构

408 主要掌握：

邻接矩阵；
邻接表；
十字链表；
邻接多重表。

前两个最重要。

五、邻接矩阵

设：

A = (a_{ij})

无权图：

a_{ij} = {1, 0, (v_{i}, v_{j}) \in E 否则

1. 无向图

矩阵必然对称：

A = A^{T}

顶点 $v_{i}$ 的度：

d (v_{i}) = j \sum a_{ij}

2. 有向图

第 $i$ 行之和：

d^{+} (v_{i})

第 $i$ 列之和：

d^{-} (v_{i})

408 真题 2013

题目：

给一个 $4 \times 4$ 邻接矩阵，要求求各顶点的度。

矩阵不对称，因此是有向图。

网站计算得到：

行和： $(2, 2, 1, 1)$ ；
列和： $(1, 2, 1, 2)$ 。

于是总度：

(3, 4, 2, 3)

答案 C。(Any Docs)

易错点

有向图中如果题目问的是“度”，而不是“出度”：

d (v) = d^{+} (v) + d^{-} (v)

不能只加一行。

六、邻接矩阵的幂：非常值得掌握

这是 2015 年 408 大题的重要知识点。

408 真题 2015

题目大意：

给定 5 个顶点的图：

写邻接矩阵 $A$ ；
求 $A^{2}$ ；
解释 $(A^{2})_{0, 3} = 3$ 的含义；
推广解释 $A^{m}$ 中元素的意义。(Any Docs)

核心结论：

(A^{m})_{ij} = 从 v_{i} 到 v_{j} 长度为 m 的通路条数

例如：

(A^{2})_{0, 3} = 3

表示：

从顶点 0 到顶点 3，恰好经过 2 条边的通路有 3 条。

为什么？

(A^{2})_{ij} = k \sum a_{ik} a_{k j}

每个非零乘积：

a_{ik} a_{k j} = 1

对应：

i \to k \to j

所以正好是在数长度为 2 的通路。

推广

(A^{m})_{ii} > 0

说明存在一条：

v_{i} \to \dots \to v_{i}

长度为 $m$ 的闭通路。

这是非常适合出新题的知识点。

七、邻接表

邻接表空间：

O (∣ V ∣ + ∣ E ∣)

特别适合稀疏图。

邻接矩阵则是：

O (∣ V ∣^{2})

所以基本判断：

稀疏图优先邻接表，稠密图邻接矩阵方便。

有向图邻接表

如果保存的是出边表：

求出度：直接数本顶点链表长度；
求入度：需要扫描所有边。

因此普通邻接表中求某个顶点入度：

O (∣ V ∣ + ∣ E ∣)

网站模拟题多次考到了这一点。(Any Docs)

八、邻接多重表

专门适合无向图。

每一条无向边只保存一个边结点，但这个边结点同时链接到两个端点的边链中。

408 真题 2024

题目：

给一个无向图的邻接多重表，问顶点 $b$ 和 $d$ 的度。

从表中还原边集后：

$b$ 关联两条边；
$d$ 关联四条边；

答案：

(2, 4)

(Any Docs)

解题原则

这种题不要死盯指针。

最稳的方法：

先把每个边结点还原成一条无向边，再数某顶点出现在多少条边里。

九、图的遍历：BFS 与 DFS

这是图这一章最基本的算法。

十、BFS 广度优先搜索

核心：

一层一层向外扩展。

需要：

队列

从 $s$ 开始：

$s$ 入队；
队头出队；
将其所有未访问邻接点标记并入队；
重复。

BFS 最重要的性质

在无权图中：

BFS 可以求从源点到各顶点的最少边数

也就是无权图单源最短路径。

模拟题：BFS 树与 DFS 树高度

网站王道卷八：

同一个连通图、同一根顶点，BFS 生成树与 DFS 生成树高度是什么关系？

答案：

h_{BFS} \leq h_{DFS}

(Any Docs)

原因是 BFS 中顶点深度恰好等于从根到该顶点的最短距离。

所以 BFS 树已经把所有顶点放到了尽量浅的位置。

十一、DFS 深度优先搜索

核心：

一条路先走到底，走不通再回溯。

最自然的实现：

递归 / 栈

判断 DFS 序列的万能方法

看到：

A, B, C, D, \dots

不要只判断“相邻两个是否有边”。

而要模拟递归栈。

如果当前顶点还有未访问邻接点：

DFS 不能无缘无故回到祖先。

408 真题 2016

题目给出有向图，问哪个不是 DFS 序列。

其中错误序列：

V_{1}, V_{2}, V_{3}, V_{4}, V_{5}

因为从 $V_{1}$ 进入 $V_{2}$ 后，存在：

V_{2} \to V_{5} \to V_{4} \to V_{3}

DFS 必须继续深入，因此应该形成类似：

V_{1}, V_{2}, V_{5}, V_{4}, V_{3}

不能访问完 $V_{2}$ 后直接跳回去访问 $V_{3}$ 。(docs.any1.tech)

十二、BFS/DFS 序列判断题

408 真题 2013

题目给一个无向图，问：

哪个序列不可能是 BFS 序列？

关键不是记邻接顺序，而是看层次：

起点为 $a$ ，假如：

L_{0} = {a}

L_{1} = {b, h, e}

那么所有 $L_{1}$ 顶点必须先于 $L_{2}$ 被发现。

因此如果出现：

a, b, c, d, h, e, \dots

其中 $c, d$ 属于第二层，而 $h, e$ 第一层还没访问，就不可能是 BFS。(docs.any1.tech)

BFS 判断口诀

先层后层，同层可换。

十三、遍历复杂度

网站 2012 真题直接考：

$n$ 个顶点、 $e$ 条边，邻接表存储的有向图执行 BFS，复杂度多少？

答案：

O (n + e)

(docs.any1.tech)

DFS 也是：

O (n + e)

如果使用邻接矩阵，无论图多稀疏，每访问一个顶点都要扫描一整行：

O (n^{2})

必背表

存储	BFS	DFS
邻接矩阵	$O (V^{2})$	$O (V^{2})$
邻接表	$O (V + E)$	$O (V + E)$

十四、图的连通性与遍历

无向图：

从一个顶点 DFS/BFS 一遍后：

若所有顶点均访问 → 连通；
否则 → 不连通。

如果对整个图：

for 每个顶点 v:
    if v 未访问:
        DFS(v)
        count++

那么：

co u n t = 连通分量数

DFS 森林中：

树的数量 = 连通分量数量

这也是很容易和树章节联合命题的地方。

十五、最小生成树 MST

这是图的第一大应用。

对于一个带权无向连通图：

从原图选出 $n - 1$ 条边，连接所有 $n$ 个顶点且没有环，使权值总和最小。

注意三个词：

连通；
无环；
权值和最小。

十六、Prim 算法

Prim 是：

扩张顶点集合。

设当前已经进入 MST 的顶点集合：

U

每一步找：

一端在 $U$ ，另一端在 $V - U$ 的最小权边。

加入另一端顶点。

可以理解成：

“从已经建好的城市网络边界继续往外扩。”

Prim 的核心限制

候选边必须横跨：

(U, V - U)

而不是全图随便拿最小边。

这就是 Prim 和 Kruskal 最大区别。

十七、Kruskal 算法

Kruskal 是：

扩张边集合 / 合并连通分量。

步骤：

所有边按权从小到大排序；
每次取最小边；
如果加入后不成环 → 加入；
如果成环 → 丢弃；
直到有 $n - 1$ 条边。

实际实现经常用：

最小堆：取得最小边；
并查集：判断两个端点是不是已在同一连通分量。

网站模拟题专门考过：Kruskal 可用最小堆高效维护候选边，而并查集用来维护顶点所属集合。(Any Docs)

十八、Prim 与 Kruskal 区别是超级高频

408 真题 2015

题目：

某条边可能成为 Kruskal 第 2 条选中的边，但从 $V_{4}$ 开始执行 Prim 时不可能成为第 2 条边，问是哪条。

答案是：

(V_{2}, V_{3})

原因：

Kruskal 可以从全图选择当前最小合法边。

但是 Prim 此时树中只有：

{V_{4}, V_{1}}

而：

(V_{2}, V_{3})

两个端点都在树外，所以 Prim 根本不能选。(Any Docs)

一句话区分

Prim：

看“顶点集合边界”。

Kruskal：

看“全局最小边，只要不成环”。

十九、MST 的唯一性

408 真题 2012

题目判断：

最小生成树的代价唯一；
权值最小的边一定出现在所有 MST；
Prim 从不同起点得到的 MST 一定相同；
Prim 与 Kruskal 总得到不同 MST。

正确只有 I。(Any Docs)

为什么？

虽然可能有多棵不同 MST，但既然它们都叫“最小”：

W (T_{1}) = W (T_{2}) = W_{m i n}

所以最小代价一定唯一。

但：

MST 结构

不一定唯一。

408 真题 2017：MST 唯一条件

题目最后问：

对任意带权连通图，什么条件保证 MST 唯一？

常用充分条件：

所有边权互不相同

则 MST 一定唯一。(Any Docs)

但注意：

这是充分条件，不是必要条件。

也就是说：

边权有重复

仍然可能只有一棵 MST。网站真题也专门强调了这一点。(Any Docs)

二十、MST 两大理论：割性质与环性质

虽然 408 不一定直接用这些名字问，但理解后 MST 判断题基本都能秒。

割性质

任意一个割：

(S, V - S)

横跨这个割的最小权边：

至少存在一棵 MST 包含它。

环性质

对于一个环：

如果某条边严格比环上的其他边都重，那么它不可能属于任何 MST。

这解释了 Kruskal：

为什么形成环时可以删掉某些大边。

二十一、最短路径

主要掌握：

BFS；
Dijkstra；
Floyd。

其中：

BFS：无权图；
Dijkstra：单源、非负权；
Floyd：所有顶点对。

二十二、Dijkstra 算法

这一部分是 408 真题超级高频。

核心维护：

d i s t [v]

表示：

当前已知的从源点 $s$ 到 $v$ 的最短距离估计。

每轮：

从未确定顶点中选择 $d i s t$ 最小的 $u$ ；
把 $u$ 的最短路永久确定；
利用 $u$ 松弛邻接点。

松弛：

d i s t [v] = min (d i s t [v], d i s t [u] + w (u, v))

最重要性质

Dijkstra 确定顶点的顺序满足：

d_{1} \leq d_{2} \leq \dots

即最短路径长度按非递减顺序被确定。

网站模拟题也直接这样考。(Any Docs)

二十三、408 真题 2012：Dijkstra 过程题

题目给带权有向图：

从源点 $a$ 出发，已知最先确定 $b, c$ ，问后面三个顶点的确定顺序。

最终：

b, c, f, d, e

因此后续：

f, d, e

(Any Docs)

怎么做最快？

考试不要反复写完整表。

画：

已确定	当前最小
$a$	$b$
$a, b$	$c$
$a, b, c$	$f$
…	…

每确定一个顶点，只更新它邻接的那些顶点。

二十四、408 真题 2021：问某一轮 dist 数组

这一题非常典型。

题目：

从顶点 1 执行 Dijkstra，第二条最短路径确定以后， $d i s t [2, 3, 4, 5]$ 为多少？

初始：

d i s t = (26, 3, \infty, 6)

先确定顶点 3：

d i s t [2] = 3 + 22 = 25

然后确定顶点 5：

d i s t [2] = min (25, 6 + 15) = 21

d i s t [4] = 6 + 8 = 14

所以：

(21, 3, 14, 6)

(Any Docs)

二十五、Dijkstra 最大陷阱：不是“每次走最短边”

408 真题 2009 大题

题目提出一种算法：

从当前顶点 $u$ 出发，每次找离 $u$ 最近的未访问顶点，一路走到目标点。问能否求最短路径？

不能。

网站给的反例可概括为：

s 1 a 100 t

另一条：

s 2 b 2 t

局部贪心会选：

s \to a

因为：

1 < 2

最后总长：

101

但真正最短：

s \to b \to t

长度：

4

(Any Docs)

所以 Dijkstra 比较的是

不是：

w (u, v)

而是：

d i s t [u] + w (u, v)

也就是源点到这里的累计距离。

这点极其重要。

二十六、Dijkstra 为什么不能处理负权边

因为一个顶点一旦被 Dijkstra 加入集合 $S$ ，算法认为：

它的最短距离已经永久确定。

如果以后通过一条负边还能降低它：

d i s t [v]_{new} < d i s t [v]_{old}

就破坏了这个贪心基础。

所以普通 Dijkstra 要求：

w (e) \geq 0

二十七、Floyd 算法

解决：

任意两点之间最短路径。

定义：

D^{(k)} [i] [j]

表示：

从 $i$ 到 $j$ ，只允许编号 $1, \dots, k$ 的顶点作为中间顶点时的最短距离。

核心递推：

D^{(k)} [i] [j] = min (D^{(k - 1)} [i] [j], D^{(k - 1)} [i] [k] + D^{(k - 1)} [k] [j])

一句话：

原来直接走，与“绕一下 $k$ ”比较。

模拟题 Floyd

网站竟成模拟三给一个 4 顶点有向图，要求求最终 dist 矩阵。

最终得到：

D = 0231 \infty 012 \infty 101 \infty 120

本质就是不断执行上面的松弛。(Any Docs)

二十八、三种最短路算法必须会区分

算法	问题	权值要求	典型复杂度
BFS	单源	无权/等权	$O (V + E)$
Dijkstra	单源	非负权	$O (V^{2})$
Floyd	多源	可含负边但不能有负环	$O (V^{3})$

模拟题中特别考了：

Floyd 并不是不能处理负权边；真正无法正常定义最短路的是存在可达负权回路的情况。(Any Docs)

二十九、拓扑排序

这是本章另一超级重点。

只针对：

有向无环图 DAG

若存在边：

u \to v

那么任一拓扑序列必须满足：

u

出现在：

v

之前。

三十、拓扑排序基本算法

采用入度法：

计算每个顶点入度；
找入度为 0 的顶点；
输出；
删除该顶点及其所有出边；
更新其他顶点入度；
重复。

若最终：

输出顶点数 < ∣ V ∣

则说明存在环。

三十一、判断某个序列是否是拓扑序列

最简单方法：

对每一条边 $u \to v$ ，检查 $u$ 是否在 $v$ 前面。

408 真题 2014

题目给图并列出若干序列。

约束包括：

3 \to 1, 3 \to 6, 1 \to 2, 1 \to 4

4 \to 2, 4 \to 6, 2 \to 5, 6 \to 5

正确序列：

3, 1, 4, 2, 6, 5

因为所有有向边均满足“起点在终点之前”。(docs.any1.tech)

选择题最快做法

不用真的跑一次拓扑算法。

逐个选项寻找一条被违反的边即可。

三十二、拓扑序列个数

408 真题 2010

约束大致为：

a \to e \to d

a \to b \to c \to d

以及：

a \to c

所以：

$a$ 必须最前；
$d$ 必须最后；
中间 $e, b, c$ 只要求 $b < c$ 。

3 个元素共有：

3! = 6

其中 $b, c$ 两种相对次序只有一半满足：

\frac{3 !}{2} = 3

所以有 3 个拓扑序列。(docs.any1.tech)

三十三、唯一拓扑序列——2024 大题核心

408 真题 2024，13 分

题目：

给定邻接矩阵存储的任意有向图，设计 uniquely(G) 判断它是否存在唯一拓扑序列。(Any Docs)

这是极有价值的一题。

唯一性的核心判定

拓扑排序每一步：

0 个入度为 0 顶点 → 有环；
1 个 → 当前选择唯一；
2 个及以上 → 当前可以任选 → 拓扑序列不唯一。

因此：

每一步必须恰好只有一个入度为 0 的顶点

才有唯一拓扑序列。

算法思路

先计算：

in d e g r ee [i]

然后循环 $n$ 次。

每轮扫描尚未删除顶点：

zeroCount = 0;

for (i = 0; i < n; i++) {
    if (!removed[i] && indegree[i] == 0) {
        zeroCount++;
        u = i;
    }
}

if (zeroCount != 1)
    return 0;

然后删掉唯一的 $u$ ：

removed[u] = 1;

for (v = 0; v < n; v++)
    if (G.Edge[u][v])
        indegree[v]--;

最终返回 1。

对于邻接矩阵：

T (n) = O (n^{2})

空间：

O (n)

(Any Docs)

三十四、拓扑排序与邻接矩阵三角性

这是一个很阴的判断题。

如果邻接矩阵的主对角线以下全部为 0：

a_{ij} = 0, i > j

所有边只能形如：

i \to j, i < j

因此不可能有：

v_{1} \to v_{2} \to \dots \to v_{1}

于是一定是 DAG。

并且：

1, 2, \dots, n

本身就是一个拓扑序列。

408 2012 真题考过这个结论。(docs.any1.tech)

但反过来：

“有拓扑序列，所以邻接矩阵一定上三角”

错误。

因为顶点编号可能乱排。

正确说法：

按某个拓扑序列给顶点重新编号后，可以把邻接矩阵变成上三角矩阵。

模拟题反复考过这个细节。(Any Docs)

三十五、DFS 与拓扑排序的联系

408 真题 2020

题目：

把递归 DFS 中“访问顶点”的输出语句移到退出递归之前再输出。若遍历 DAG 的全部顶点，所得序列是什么？

答案：

逆拓扑序列

(Any Docs)

为什么？

对于：

u \to v

DFS 从 $u$ 进入 $v$ 。

只有：

v

及其后继全部完成，才返回 $u$ 。

所以按退出顺序：

v

在：

u

之前。

于是得到：

逆拓扑序

把这个退出顺序反转：

拓扑序

这是算法题很喜欢的关联。

三十六、关键路径 AOE 网

这是本章计算量最大、但套路最固定的内容。

AOE 网：

顶点表示事件，边表示活动，边权表示活动持续时间。

工程开始：

源点。

工程完成：

汇点。

三十七、关键路径本质

关键路径不是最短路。

而是：

源点到汇点的最长路径

为什么？

因为某个工程只有所有前置活动都完成后才能继续。

所以工程总时间被最慢的那条路径卡住。

408 真题 2020

问：

AOE 网中什么叫关键路径？

正确：

从源点到汇点，路径长度最长的路径。

(Any Docs)

注意不是：

边数最多。

看的是边权总和。

三十八、事件最早发生时间 $v e$

正向拓扑计算。

源点：

v e (s) = 0

对顶点 $j$ ：

v e (j) = i \to j max {v e (i) + w (i, j)}

为什么是 max？

因为 $j$ 必须等所有前置活动完成。

例如：

A 3 C

B 7 C

如果：

v e (A) = 2, v e (B) = 4

那么：

v e (C) = max (2 + 3, 4 + 7) = 11

三十九、事件最迟发生时间 $v l$

先得到工程总工期：

T = v e (汇点)

令：

v l (汇点) = T

然后逆拓扑：

v l (i) = i \to j min {v l (j) - w (i, j)}

为什么是 min？

因为只要错过任意一个后继活动允许的最晚开始时刻，工程就会延期。

四十、活动的最早/最迟开始时间

对活动：

a_{k} = ⟨ i, j ⟩

持续时间：

w (i, j)

最早开始：

e (k) = v e (i)

最迟开始：

l (k) = v l (j) - w (i, j)

时间余量：

d (k) = l (k) - e (k)

如果：

d (k) = 0

则该活动为：

关键活动

四十一、408 真题 2019：求活动 d 的最早、最迟开始时间

网站题目计算得到：

v e (2) = 12

活动 $d$ ：

2 \to 4

持续时间：

7

所以：

e (d) = v e (2) = 12

而：

v l (4) = 21

所以：

l (d) = 21 - 7 = 14

答案：

12, 14

(Any Docs)

四十二、408 真题 2022：求最大时间余量

题目给一个有 10 个活动的 AOE 网，问：

$c, g, h, j$ 中哪一个时间余量最大？

网站计算：

Δ c = 0

Δ g = 6

Δ h = 2

Δ j = 2

所以：

g

最大余量为：

6

(Any Docs)

模拟题也专门考过同类“时间余量最大”活动计算。(Any Docs)

四十三、多条关键路径是最容易丢分的地方

408 真题 2013

题目问：

同时加快哪些活动，可以保证缩短整个工程工期？

该图存在 3 条关键路径。网站分析得到，要让工程工期缩短，所加速的活动集合必须覆盖所有关键路径，其中同时加快 $d$ 和 $f$ 可以做到这一点。(Any Docs)

为什么“缩短一个关键活动”不一定缩短工程？

假设两条关键路径：

P_{1} = 20

P_{2} = 20

将只属于 $P_{1}$ 的活动缩短 3：

P_{1} = 17

但是：

P_{2} = 20

所以工期还是：

20

因此：

缩短任一关键活动，不一定缩短工期

这正是 2020 真题的陷阱。(Any Docs)

四十四、图算法设计题：近年非常值得重视

这部分复习时不能只刷选择题。

从网站真题能看到很明显的命题模式：

给一种图存储结构 + 定义某种图性质 → 设计 $O (V^{2})$ 或 $O (V + E)$ 算法。

四十五、2021 真题：EL 路径判定

题目大意：

已知无向连通图，如果奇数度顶点数量是不大于 2 的偶数，则存在包含全部边的 EL 路径。给邻接矩阵，设计函数判断是否存在 EL 路径。(Any Docs)

其实就是欧拉通路性质。

对于无向连通图：

欧拉回路：

所有顶点度均为偶数

欧拉通路：

奇度顶点数量为 0 或 2

算法

逐行求度：

d e g r e e_{i} = j \sum A [i] [j]

统计：

d e g r e e_{i} mod 2 = 1

的顶点数。

若：

o dd = 0 或 o dd = 2

返回 1。

复杂度

邻接矩阵：

O (V^{2})

额外空间：

O (1)

(Any Docs)

四十六、2023 真题：K 顶点

定义：

有向图中出度大于入度的顶点称为 K 顶点。

要求：

输出所有 K 顶点；
返回 K 顶点数量。

邻接矩阵中：

d^{+} (v_{i}) = j \sum A [i] [j]

d^{-} (v_{i}) = j \sum A [j] [i]

若：

d^{+} (v_{i}) > d^{-} (v_{i})

输出该顶点。(Any Docs)

时间：

O (V^{2})

空间：

O (1)

这题真正想考什么？

不是 K 顶点。

“ K 顶点”只是现场定义的新概念。

真正考的是：

是否理解邻接矩阵的行和、列和分别代表什么。

因此以后看到陌生定义不要慌。

先把定义翻译成：

度数；
可达；
连通；
入度；
出度；
路径；
环；

这些基本量，再写算法。

四十七、2024 真题：唯一拓扑序列

这题同样如此。

表面背景是神舟十七号子工程前导关系，实际上就是：

邻接矩阵 + 入度 + Kahn 拓扑排序 + 唯一性判断。

(Any Docs)

这代表了当前 408 图论算法题非常重要的一种趋势：

不给出背某个固定算法模板，而是要求将教材算法稍微改造一下。

例如：

普通拓扑排序 → 判断是否唯一；
普通求度 → 判断特殊顶点；
普通 DFS → 判断某种性质；
BFS → 求某种最少步数；
Dijkstra → 输出路径/前驱；
邻接矩阵 → 统计满足条件的顶点。

四十八、2011 真题：压缩存储 + AOE + 关键路径

这是一道非常有综合价值的题。

题目给：

6 个顶点的有向带权图，其邻接矩阵为上三角矩阵，把主对角线以上元素按行优先压缩成一维数组。

要求：

写邻接矩阵；
画图；
求关键路径及长度。(Any Docs)

网站恢复出的边包括：

0 \to 1 (4), 0 \to 2 (6)

1 \to 2 (5)

2 \to 3 (4), 2 \to 4 (3)

3 \to 5 (3), 4 \to 5 (3)

计算：

v e (0) = 0

v e (1) = 4

v e (2) = max (6, 4 + 5) = 9

v e (3) = 13

v e (4) = 12

v e (5) = max (13 + 3, 12 + 3) = 16

因此关键路径：

0 \to 1 \to 2 \to 3 \to 5

长度：

16

(Any Docs)

这类题说明：

408 可以把“矩阵压缩 + 图的建立 + AOE”揉成一道题。

四十九、2014 真题：图与计算机网络联合命题

题目把 OSPF 路由器网络抽象成图：

判断逻辑结构；
设计链式存储结构保存链路状态；
按 Dijkstra 求 R1 到各子网的最短路径。(Any Docs)

这题非常能说明 408 的特点：

四科知识可以交叉。

OSPF 的链路状态数据库，本质就是：

带权图

OSPF 计算最短路径，本质上对应：

Dijkstra

网站最后算出 R1 到若干网络的费用，例如经 R3 的路径费用为 3，经 R2、R4 的路径费用为 8。(Any Docs)

所以数据结构里的图不能和计算机网络完全割裂学习。

五十、2018 真题：MST + 网络 TTL

还有一道综合题：

8 个城市铺设光纤，边权为成本：

求所有最经济方案；

说明存储结构和使用的算法；

再根据形成的网络回答 TTL 是否足以让 IP 分组到达。

本质：

前半题：

MST

后半题：

计算机网络 IP/TTL

网站指出该图甚至存在两种最经济铺设方案，说明这道题同时考了：

MST 可能不唯一。(Any Docs)

五十一、这一章的“算法选择题”怎么秒判

建议建立下面这张条件反射表。

题目关键词	第一反应
无权图最少经过几条边	BFS
从一个源点到其他点、边权非负	Dijkstra
任意两个顶点最短距离	Floyd
最低成本连接所有顶点	MST
从某顶点集合逐步扩张	Prim
全局按边权排序、避免成环	Kruskal
先修关系、依赖关系	拓扑排序
是否存在环	DFS / 拓扑排序
工程最短完工时间	关键路径
活动能延迟多久	时间余量
无向图连通性	BFS/DFS
有向图相互可达	强连通
度数与边数	握手定理
邻接矩阵 $A^{k}$	长度为 $k$ 的通路数量

五十二、复杂度必须集中背

这部分 408 很喜欢直接问。

BFS / DFS

邻接表：

O (V + E)

邻接矩阵：

O (V^{2})

拓扑排序

邻接表：

O (V + E)

408 2016 真题直接考过。(Any Docs)

Prim

教材邻接矩阵实现通常：

O (V^{2})

因此更适合：

稠密图。

Kruskal

主要时间用于排序：

O (E lo g E)

更适合：

稀疏图。

Dijkstra

教材数组 + 邻接矩阵：

O (V^{2})

Floyd

三重循环：

O (V^{3})

空间：

O (V^{2})

五十三、这章最容易混淆的 10 组概念

1. 连通图 vs 强连通图

无向图主要讲：

连通。

有向图主要讲：

强连通。

2. 路径 vs 回路

路径：

v_{0} \to v_{1} \to \dots \to v_{k}

回路：

v_{0} = v_{k}

3. BFS vs Dijkstra

BFS：

无权/等权。

Dijkstra：

非负带权。

4. Dijkstra vs Floyd

Dijkstra：

单源。

Floyd：

所有点对。

5. Prim vs Kruskal

Prim：

扩顶点。

Kruskal：

选边并合并连通分量。

6. 最短路径 vs 最小生成树

最短路径：

让某两个点之间的路径最短。

MST：

让连接所有顶点的总成本最小。

MST 中 $s \to t$ 的路径：

不保证是原图的最短路径。

7. 拓扑排序 vs DFS

拓扑排序：

DAG 上的偏序线性化。

DFS：

图的遍历方式。

不过 DFS 退出序逆序可以得到拓扑序。

8. AOV vs AOE

AOV：

顶点表示活动。

主要解决：

拓扑排序

AOE：

边表示活动。

主要解决：

关键路径

9. “关键路径”里的最长 vs Dijkstra 的最短

AOE：

max

Dijkstra：

min

千万别混。

10. MST 唯一 vs MST 权值唯一

MST 本身：

可能多棵。

最小总代价：

一定唯一。

五十四、建议把图题分成 8 个题型模板

根据本站真题与模拟题，本文将这样归纳。

模板 A：度数 / 边数 / 连通性

看到：

度；
奇度；
边数；
顶点数；
连通；

优先写：

\sum d (v) = 2 E

E_{连通} \geq V - 1

以及：

E_{m a x, 不连通} = (2 V - 1)

代表题：

2009 握手定理；
2010 保证连通；
2017 度数反推顶点；
2022 $V, E$ 与连通性。(docs.any1.tech)

模板 B：存储结构

看到邻接矩阵：

先判断：

A = A^{T} ?

然后想到：

行和 = 出度

列和 = 入度

以及：

(A^{m})_{ij}

的通路含义。

代表题：

2013 邻接矩阵求度；
2015 邻接矩阵幂；
2024 邻接多重表。(Any Docs)

模板 C：BFS/DFS

BFS：

按层。

DFS：

沿路径深入。

代表题：

2013 判断 BFS 序列；
2015 DFS 可能序列数量；
2016 判断 DFS 序列；
模拟题 BFS/DFS 树高度。(Any Docs)

模板 D：MST

Prim：

U \leftrightarrow V - U

Kruskal：

最小边 + 不成环

代表题：

2012 MST 性质；
2015 Prim/Kruskal 差异；
2017 MST 唯一性；
2018 光纤网络综合题；
2020 Kruskal 选边顺序。(Any Docs)

模板 E：Dijkstra

每轮：

u = ar g v \in / S min d i s t [v]

再松弛：

d i s t [v] = min (d i s t [v], d i s t [u] + w (u, v))

代表题：

2012；
2016；
2021；
2009 算法反例；
2014 OSPF 综合题。(Any Docs)

模板 F：Floyd

只背一个式子：

D [i] [j] = min (D [i] [j], D [i] [k] + D [k] [j])

模拟题主要考：

中间矩阵 / 最终矩阵 / 负权性质。(Any Docs)

模板 G：拓扑排序

每轮删：

in d e g r ee = 0

唯一拓扑序：

每轮恰好一个零入度顶点

代表题：

2010 拓扑序个数；
2012 上三角矩阵；
2014 判断拓扑序列；
2018 判断拓扑序列；
2020 DFS 与逆拓扑；
2021 唯一拓扑序；
2024 唯一拓扑序算法设计。(Any Docs)

模板 H：关键路径

按顺序机械计算：

v e \to v l \to e \to l \to l - e

其中：

v e (j) = max (v e (i) + w_{ij})

v l (i) = min (v l (j) - w_{ij})

e (i, j) = v e (i)

l (i, j) = v l (j) - w_{ij}

l - e = 0 \Rightarrow 关键活动

代表题：

2013 多关键路径；
2019 最早/最迟时间；
2020 关键路径概念；
2022 最大时间余量；
2011 综合大题。(Any Docs)

五十五、预测几种很值得防的变式

结合网站中的真题演化，下面几种很适合以后继续出。

变式 1：唯一拓扑序 → 输出拓扑序并判断唯一

把 2024 真题扩展成：

若唯一则输出；若不唯一返回多个候选顶点。

核心仍然是统计零入度顶点数量。

变式 2：邻接矩阵 → 满足某种度数条件的顶点

2023 已经考：

d^{+} > d^{-}

以后完全可能定义：

d^{+} = d^{-}

或者：

∣ d^{+} - d^{-} ∣ \leq 1

算法结构几乎不变。

变式 3：BFS 求无权最短路径并输出路径

除了：

d i s t [v]

再增加：

p r e [v]

发现 $v$ 时：

p r e [v] = u

最后从终点沿 pre 反向恢复路径。

变式 4：判断图是否为树

对于无向图：

连通且 E = V - 1

可以：

DFS/BFS 判断连通；
再判断边数。

也可以 DFS 检测环。

变式 5：关键路径有几条

先算出所有关键活动，即：

l - e = 0

它们组成“关键子图”。

再统计：

从源点到汇点的路径数。

这比单纯求一条关键路径再上一个台阶。

变式 6：MST 修改一条边权后是否改变

模拟题已经出现一些类似性质判断。(Any Docs)

例如：

降低原 MST 中一条边的权值。

原 MST 一定仍然是 MST。

因为它只会变得更便宜。

但如果：

降低一条非 MST 边权值。

就可能改变 MST。

五十六、最后给出一份考前速记版

这一章如果只剩 10 分钟复习，就记下面这些。

\sum d (v) = 2 E

\sum d^{+} = \sum d^{-} = E

连通无向图 E \geq V - 1

E_{保证连通} > (2 V - 1)

邻接矩阵：

有向图行和 = 出度，列和 = 入度

(A^{k})_{ij} = 长度为 k 的 i \to j 通路数

遍历：

BFS= 队列 = 分层 = 无权最短路

DFS= 递归 / 栈 = 深入回溯

MST：

Prim 扩顶点， Kruskal 选边

Dijkstra：

d i s t [v] = min (d i s t [v], d i s t [u] + w_{uv})

Floyd：

D [i] [j] = min (D [i] [j], D [i] [k] + D [k] [j])

拓扑：

每轮删入度 0 顶点

唯一拓扑：

每轮恰有 1 个入度 0 顶点

关键路径：

v e = max

v l = min

e = v e (i)

l = v l (j) - w (i, j)

l - e = 0 \Rightarrow 关键活动

以及最后一个极其容易错的：

关键路径是最长路径，不是最短路径

从本站目前整理的真题来看，第 6 章最值得重点训练的优先级本文将排成：

拓扑排序 > 最短路径 \approx 关键路径 \approx MST > BFS/DFS > 存储结构 > 基本概念

但基本概念和邻接矩阵又非常容易被包装进算法大题，所以不能只会四大应用。尤其是 2015 邻接矩阵幂、2021 EL 路径、2023 K 顶点、2024 唯一拓扑序列这四道题，建议把它们当成这一章算法题的四个核心母题来掌握。(Any Docs)

数据结构第 6 章：图

On this page