图的基本应用

本节导读

大纲列的图的基本应用有四项：最小（代价）生成树、最短路径、拓扑排序、关键路径。这四个算法都有固定的手工推演格式，选择题问某一步的结果，综合应用题可能要求写出完整过程。

学完你应该能对一张给定的图按步骤写出 Prim、Kruskal、Dijkstra 的过程表，写出拓扑序列，并列表算出 AOE 网的 ve、vl、e、l 和关键路径。

最小生成树

带权连通无向图的所有生成树中，各边权值之和最小的叫最小生成树。它可能不唯一，但权值之和是唯一的；各边权值互不相同时，最小生成树唯一。

算法	做法	时间复杂度	适合
Prim	从一个顶点出发，每次在「一端在树内、一端在树外」的边中选权值最小的，把树外那个顶点并进来	$O(n^2)$O(n2)，与边数无关	稠密图
Kruskal	把边按权值从小到大排序，依次考察，不与已选的边构成回路就选入，选够 n − 1 条为止	$O(e\log_2 e)$O(elog2​e)，判回路用并查集	稀疏图

两种算法都是贪心：每一步都选当前能选的最小边，可以证明结果的总权值最小。

最短路径

算法	解决的问题	做法要点	时间复杂度	限制
BFS	无权图单源	按层扩展	邻接表 $O(n + e)$O(n+e)	只适用于无权图
Dijkstra	带权图单源	每次从未确定的顶点中选 dist 最小的，确定它，再用它更新其余顶点的 dist	$O(n^2)$O(n2)	不能有负权边
Floyd	每一对顶点之间	依次以每个顶点 k 为中转，若 $A[i][k] + A[k][j] \lt A[i][j]$A[i][k]+A[k][j]<A[i][j] 就更新	$O(n^3)$O(n3)	可以有负权边，不能有负权回路

Dijkstra 不能处理负权边，是因为一个顶点一旦被「确定」就不再修改，而负权边可能让之后经过别的顶点绕过来的路径更短。

拓扑排序

用顶点表示活动、有向边表示活动之间的先后关系的有向无环图叫 AOV 网。拓扑排序：

1. 选一个入度为 0 的顶点输出；
2. 删去它和它发出的所有边（相关顶点的入度减 1）；
3. 重复，直到输出全部顶点，或者找不到入度为 0 的顶点。

后一种情况说明图里有回路，所以拓扑排序可以判断有向图是否有环。拓扑序列一般不唯一。用邻接表存储、用栈或队列暂存入度为 0 的顶点时，时间复杂度为 $O(n + e)$O(n+e)。

关键路径

用边表示活动、边上的权表示活动持续时间、顶点表示事件的带权有向无环图叫 AOE 网。从源点到汇点的路径中，长度最长的叫关键路径，它的长度就是完成整个工程的最短时间；关键路径上的活动叫关键活动。

量	含义	求法
ve(k)	事件 k 最早发生时间	源点为 0，按拓扑序取 $\max\{ve(j) + w(j,k)\}$max{ve(j)+w(j,k)}
vl(k)	事件 k 最迟发生时间	汇点 vl = ve，按逆拓扑序取 $\min\{vl(j) - w(k,j)\}$min{vl(j)−w(k,j)}
e(i)	活动 $a_i = \langle j, k \rangle$ai​=⟨j,k⟩ 最早开始时间	e(i) = ve(j)
l(i)	活动最迟开始时间	l(i) = vl(k) − w(j, k)
d(i)	时间余量	d(i) = l(i) − e(i)，等于 0 的是关键活动

缩短关键活动的时间可以缩短工期，但缩短到一定程度它可能不再是关键活动；有几条关键路径时，只缩短其中一条上的活动，工期不变。

易错提醒

• ❌ Kruskal 算法每次选与当前树相连的最小边。✅ 那是 Prim；Kruskal 在全部边里选最小的、不构成回路的边。因为 Kruskal 中间过程可以是若干棵不相连的树。

• ❌ Dijkstra 算法可以用于有负权边的图。✅ 有负权边时 Dijkstra 可能出错，要用 Floyd 等算法（且不能有负权回路）。因为已确定的顶点不会再被修改。

• ❌ 关键路径是从源点到汇点的最短路径。✅ 是最长路径。因为所有活动都完成工程才算完，最长的那条决定工期。

• ❌ 求 vl 时也取 max。✅ ve 取 max（等所有前驱都完成），vl 取 min（不能耽误任何一个后继）。因为两者一个往前推、一个往后推。

• ❌ 拓扑排序输出了部分顶点后找不到入度为 0 的顶点，说明算法写错了。✅ 说明图中有回路。因为回路上的顶点入度永远减不到 0。

例题精讲

例题 1（最小生成树）

无向图的边及权值为：(A,B) 7、(A,C) 2、(A,D) 6、(B,C) 5、(B,E) 4、(C,D) 3、(C,E) 8、(D,F) 9、(E,F) 1、(C,F) 10。分别用 Kruskal 算法和从 A 出发的 Prim 算法写出选边次序。

答题要点示范：Kruskal：按权值依次选 (E,F) 1、(A,C) 2、(C,D) 3、(B,E) 4、(B,C) 5，已经 5 条边、连通 6 个顶点，结束。Prim（从 A）：(A,C) 2 → (C,D) 3 → (C,B) 5 → (B,E) 4 → (E,F) 1。两者得到同一棵树，权值和 15。

点评：Prim 第三步候选边有 (A,B) 7、(B,C) 5、(C,E) 8、(D,F) 9、(C,F) 10，选 5；之后 (B,E) 4 才成为「一端在树内」的边。

例题 2（Dijkstra）

有向带权图：A→B 4、A→C 1、C→B 2、B→D 1、C→D 5、D→E 3、C→E 8。求 A 到其余顶点的最短路径长度。

答题要点示范：

步骤	确定的顶点	B	C	D	E
初始	A	4	1	∞	∞
1	C	3（经 C）	1	6	9
2	B	3	—	4（经 B）	9
3	D	—	—	4	7（经 D）
4	E	—	—	—	7

最短路径长度：B 3、C 1、D 4、E 7，确定的次序是 C、B、D、E。

例题 3（关键路径）

AOE 网有事件 1 至 6，活动：a：1→2 用时 4，b：1→3 用时 3，c：2→4 用时 5，d：3→4 用时 6，e：3→5 用时 4，f：4→6 用时 3，g：5→6 用时 7。求关键路径。

答题要点示范：ve：1 为 0，2 为 4，3 为 3，4 为 max(4 + 5, 3 + 6) = 9，5 为 7，6 为 max(9 + 3, 7 + 7) = 14。vl：6 为 14，5 为 7，4 为 11，3 为 min(11 − 6, 7 − 4) = 3，2 为 6，1 为 0。余量：a、c、d、f 都是 2，b、e、g 为 0。关键路径 1→3→5→6，长度 14。

本节小结

• 最小生成树：Prim 选「树内到树外」的最小边，$O(n^2)$O(n2) 适合稠密图；Kruskal 全局选最小且不成环的边，适合稀疏图。
• 最短路径：Dijkstra 单源、无负权边、$O(n^2)$O(n2)；Floyd 每对顶点、$O(n^3)$O(n3)、不能有负权回路；无权图用 BFS。
• 拓扑排序：反复输出入度为 0 的顶点；输出不完说明有回路；序列一般不唯一。
• 关键路径：ve 取 max、vl 取 min，余量为 0 的是关键活动；关键路径是最长路径。