🕸️ 408 图论核心算法速查笔记
核心痛点解决
图论算法极容易混淆(Prim/Kruskal/Dijkstra/Floyd)。本笔记按 408 考察频率 排序。 【口诀 + 可折叠手算例子 + 破局思路 + 变体预警】,让你看到题目就能瞬间提取出“该用哪个算法”。
1. 广度优先搜索(BFS)—— 考察频率:⭐⭐⭐⭐⭐
一句话记忆
“层序遍历,无权图的最短路径”。从起点开始,一圈一圈往外扩,第一次遇到的节点,路径一定最短。
📝 小题自测(点击展开看手算与破局)
题目:已知无向连通图 G 中各边的权值均为 1,下列算法中,一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是( )。 I. 普利姆算法 II. 克鲁斯卡尔算法 III. 图的广度优先搜索 A. 仅 I B. 仅 III C. 仅 II 和 I D. I, II, III
手算与推导:
- 题目强调“各边权值均为 1”(无权图)。求“某顶点到其余各顶点的最短路径”。
- I 和 II 破局:普利姆(Prim)和克鲁斯卡尔(Kruskal)是最小生成树算法。它们的目标是“用最小的代价把所有点连起来”,求的是整体连通性的最优解,并不保证单源到某点的路径最短(只保证总权重和最小)。
- III 破局:广度优先搜索(BFS)的本质是“层序遍历”。从起点开始,第一层是距离为 1 的点,第二层是距离为 2 的点……只要边权为 1,BFS 第一次访问到某个节点时,走过的边数就是最短路径。
结论:选 B。
变体预警
如果题目说“各边权值不全为 1”(带权图),BFS 就失效了,必须用 Dijkstra(非负权)或 Floyd。408 选择题最爱考这个“权值均为 1”的前提。
2. 迪杰斯特拉(Dijkstra)—— 考察频率:⭐⭐⭐⭐⭐
一句话记忆
“单源最短路径,贪心选最近”。从起点开始,每次从未确定的点中选一个距离最小的,然后用它去更新邻居。
📝 小题自测(点击展开看手算与破局)
题目:用 Dijkstra 算法求下图中从 V1 到其余各顶点的最短路径。 假设带权图结构如下:
手算步骤:
- 初始:dist = [0, ∞, ∞, ∞],确定源点 V1。
- 用 V1 更新邻居:dist = [0, 2, ∞, 1]。选最小的未确定点 V4(1),确定 V4。
- 用 V4 更新邻居:V4→V2(2+1=3,大于现有2,不更新),V4→V3(1+1=2,小于∞,更新)。dist = [0, 2, 2, 1]。选最小的未确定点 V2(2),确定 V2。
- 用 V2 更新邻居:V2→V3(2+3=5,大于现有2,不更新)。dist = [0, 2, 2, 1]。确定 V3。
结论:最终 dist = [0, 2, 2, 1](V1→V4 为 1,V1→V2 为 2,V1→V3 经 V4 为 2)。
⚠️ 避坑:Dijkstra 是贪心算法,不能处理负权边。如果题目出现负权边,直接排除 Dijkstra。
变体预警
408 常考“Dijkstra 算法在什么时候会失效?”答案就是存在负权边时。带负权的最短路径要用 Floyd 或 Bellman-Ford。
3. 普利姆(Prim)与克鲁斯卡尔(Kruskal)最小生成树 —— 考察频率:⭐⭐⭐⭐
核心机制一句话秒杀
- Prim(加点法 · 滚雪球):从源点出发,时刻保持一棵唯一的连通生长树,每次从连接“已选点”与“未选点”的跨界割边中挑最小边把新点拉入。适合稠密图(时间复杂度 ,与边数无关)。
- Kruskal(加边法 · 森林合并):全局按权值贪心升序挑边,只要权值最小就选,根本不管跟当前树连不连得上!允许中间状态呈现多棵孤立树构成的森林,依赖并查集防环。适合稀疏图(时间复杂度 )。
📝 核心手算小题自测:同一图下 Prim vs Kruskal 对决(点击展开看手算与破局)
题目:无向图有 4 个顶点 V1~V4,边及权值:V1-V2(1), V1-V3(3), V2-V3(2), V2-V4(4), V3-V4(5)。分别用 Prim 算法(从 V1 开始)和 Kruskal 算法求最小生成树。
一、Prim 算法(加点法)手算推导:
- 初始:树点集 。候选跨界割边:。选最小割边 ,加入点 ,树扩大为 。
- 当前树:。候选跨界割边:。选最小割边 ,加入点 ,树扩大为 。
- 当前树:。候选跨界割边:。选最小割边 ,加入点 ,全部 4 个顶点集齐,算法终止!
- Prim 结论:MST 边集 = ,总权重 = 。
二、Kruskal 算法(加边法)手算推导:
- 全局边权升序排序:(1) , (2) , (3) , (4) , (5) 。
- 选 (1) :两端点分属不同连通块,加入!生成初始小树 。
- 选 (2) : 为孤立点,加入!连通块扩大为 。
- 选 (3) :⚠️ 并查集检测
Find(V1) == Find(V3),两端已在同一子树,选入必形成回路 ,果断跳过淘汰!- 选 (4) : 为孤立点,加入!已选满 条边,算法终止。
- Kruskal 结论:MST 边集 = ,总权重 = 。
💡 核心释疑(学长一锤定音): Kruskal 选权值最小的边,根本不管它跟当前树连不连得上!哪怕天各一方也直接选!只要并查集判定两端点不属于同一集合(不构成环),就果断加入!中间状态完全允许呈现“孤立子树森林”。
变体预警(408 连环陷阱)
- “某算法在执行过程中的某一时刻,已选的边集可能包含若干棵互不连通的子树,该算法是?” → 毫无悬念,必选 Kruskal!
- “某算法在任何时刻选出的边集始终构成一棵连通的树,该算法是?” → 毫无悬念,必选 Prim!
- 如果题目说“各边权值均为 1”,Prim 和 Kruskal 都能求出最小生成树,但它们求的是整体连通代价最小,不是单源最短路径(单源最短路径边权为 1 必须用 BFS)。
5. 弗洛伊德(Floyd)—— 考察频率:⭐⭐⭐⭐
一句话记忆
“多源最短路径,动态规划”。用一个二维矩阵,不断尝试“经过中间点 k 会不会更短”。
📝 小题自测(点击展开看手算与破局)
题目:有 3 个顶点 V1, V2, V3,邻接矩阵初始为:
[[0, 2, ∞], [∞, 0, 3], [4, ∞, 0]]用 Floyd 算法求最终的最短路径矩阵。
手算步骤:
- 初始矩阵:
[0, 2, ∞][∞, 0, 3][4, ∞, 0]- 尝试经过 V1:V2→V1→V3 = ∞+∞ = ∞,不更新;V3→V1→V2 = 4+2 = 6 < ∞,更新。
- 尝试经过 V2:V1→V2→V3 = 2+3 = 5 < ∞,更新。
- 尝试经过 V3:V2→V3→V1 = 3+4 = 7 < ∞,更新。
结论:最终矩阵:
[0, 2, 5][7, 0, 3][4, 6, 0]
变体预警
Floyd 的时间复杂度是 O(n³),适合多源最短路径。408 常考“Floyd 算法可以处理负权边,但不能处理负权回路”。
6. 拓扑排序(Topological Sort)—— 考察频率:⭐⭐⭐⭐
一句话记忆
“有向无环图,找入度为 0 的点”。每次选一个入度为 0 的顶点输出,然后删除它和它的所有出边。
📝 小题自测(点击展开看手算与破局)
题目:有向图顶点 A, B, C, D,边:A→B, A→C, B→D, C→D。求拓扑排序序列。
手算步骤:
- 统计各顶点初始入度:A:0, B:1, C:1, D:2。
- 全图仅 A 入度为 0,首选 A 输出。删除 A 以及出边 A→B, A→C。此时各点入度变为 B:0, C:0, D:2。
- 此时 B 和 C 入度均为 0,输出顺序出现分支:
- 若先选 B 输出:删除出边 B→D,此时 C:0, D:1;接下来只能选 C 输出,删除 C→D,D:0,最后输出 D → 得到
A, B, C, D;- 若先选 C 输出:删除出边 C→D,此时 B:0, D:1;接下来只能选 B 输出,删除 B→D,D:0,最后输出 D → 得到
A, C, B, D。结论:拓扑序列为
A, B, C, D或A, C, B, D(结果不唯一)。⚠️ 避坑:拓扑排序的结果不唯一。如果题目问“是否存在拓扑排序”,等价于问“图中是否有环(DAG 判定)”。
变体预警
408 常考“拓扑排序和逆拓扑排序的区别”。逆拓扑排序是每次选出度为 0 的点输出并删除入边。
7. 关键路径(Critical Path)—— 考察频率:⭐⭐⭐
一句话记忆
“AOE 网,源点到汇点的最长路径”。最长路径的长度决定了整个工程的最短完成时间(工期)。
📝 小题自测(点击展开看手算与破局)
题目:AOE 网中,从源点 V1 到汇点 V4 有两条路径:
- 路径 1:
V1 → V2 → V4(其中V1→V2权值为 3,V2→V4权值为 2,总长 5)- 路径 2:
V1 → V3 → V4(其中V1→V3权值为 4,V3→V4权值为 3,总长 7) 求关键路径及工程最短完成时间。
手算步骤:
- 计算每个事件(顶点)的最早发生时间
ve(顺拓扑序取最大值):
ve(V1) = 0ve(V2) = 0 + 3 = 3ve(V3) = 0 + 4 = 4ve(V4) = max(ve(V2) + 2, ve(V3) + 3) = max(5, 7) = 7- 关键路径是源点到汇点的最长路径,即
V1 → V3 → V4(长度 7)。结论:关键路径是
V1 → V3 → V4,工程最短完成时间是7。⚠️ 避坑:关键路径是最长路径,求的是最短工期!关键路径上的所有活动均为关键活动,其
e(i) = l(i)(时间余量d(i) = l(i) - e(i) = 0,没有机动时间)。
变体预警(408 最爱考的 3 条铁律)
- 缩短某条关键活动的时间,不一定能缩短整个工期:因为缩短太多可能会使原本的关键路径变成非关键路径;或者当图中存在多条并列的关键路径时,只缩短其中一条关键路径上的活动,总工期完全不变!
- 要缩短整个工期,必须同时缩短所有关键路径上的关键活动(或缩短所有关键路径的公共关键活动)。
- 延长任意一条关键活动的时间,整个工程工期一定延长!
📋 图论算法速查表(重点背诵)
| 算法 | 目的 | 适用图 | 时间复杂度 | 核心口诀 |
|---|---|---|---|---|
| BFS | 单源最短路径 | 无权图 | O(V+E) | 层序遍历,边权为 1 |
| Dijkstra | 单源最短路径 | 非负权图 | O(V²) | 贪心选最近,不能负权 |
| Floyd | 多源最短路径 | 带权图 | O(V³) | 动态规划,三重循环 |
| Prim | 最小生成树 | 稠密图 | O(V²) | 加点法,选最小边 |
| Kruskal | 最小生成树 | 稀疏图 | O(E log E) | 加边法,判环 |
| 拓扑排序 | 有向无环图排序 | DAG | O(V+E) | 入度为 0 输出 |
| 关键路径 | AOE 网工期 | DAG | O(V+E) | 最长路径,无机动 |
易混淆对比(408 最爱考)
- Prim vs Dijkstra:Prim 求的是“连通所有点的最小总代价”,Dijkstra 求的是“从起点到各点的最短路径”。两者都是贪心,都从已选点集出发,但目标不同。
- BFS vs Dijkstra:BFS 是 Dijkstra 在“边权为 1”时的特例。BFS 用队列,Dijkstra 用优先队列。
- Kruskal vs Prim:Kruskal 适合稀疏图,Prim 适合稠密图。
- Floyd vs Dijkstra:Floyd 是多源,Dijkstra 是单源;Floyd 可以处理负权边,Dijkstra 不能。
- 拓扑排序 vs 关键路径:拓扑排序是求“一个可行的执行顺序”,关键路径是求“最短完成时间”。关键路径上的活动没有机动时间。
📝 考前复习建议
考前复习建议
- 画图:Prim/Kruskal 手动画生成树过程;Dijkstra/Floyd 手动更新 dist 矩阵。
- 背表:上面的速查表和易混淆对比,考前看一遍,选择题直接秒杀。
- 看变体预警:每个算法下的
[!warning]块,都是选择题的陷阱所在。- 抓前提:题目中的“权值均为 1”、“非负权”、“稀疏图/稠密图”是关键判断依据。