第二十九课最小生成树实战——Kruskal 与 Prim本课核心Kruskal按边从小到大选不能成环。Prim从一个点出发每次找最近的新点。一、先用一个故事回顾最小生成树假设有 5 个城市A —— B —— C \ | / \ | / D —— E城市之间有很多条公路每条公路都有一个建设费用。现在政府提出一个问题我要让所有城市都连起来但是修路的钱最少应该修哪些路这就是最小生成树问题。最小生成树问题的定义是在一个含有 n 个顶点的连通网中选择 n−1 条边构成一棵生成树并使这些边的权值之和最小就是最小生成树。所以我们马上得到三个关键词① 所有点都要连接不能漏掉城市。② 不能有环否则就不是树。③ 总费用最小这是“最小”二字的含义。二、为什么一定是 n-1 条边这是 CSP-J 初赛非常重要的结论。如果有n 个顶点那么一棵树一定有n - 1 条边例如3个点 A —— B | C有3 - 1 2条边5个点A —— B —— C | D —— E需要5 - 1 4条边因此n 个顶点的生成树一定有 n−1 条边。CSP-J专门考到了这个知识点。三、为什么不能“最小的边全部选”这是学习最小生成树最容易掉进去的坑。假设有A —— B 1 B —— C 2 A —— C 3我们按照从小到大1A-B 2B-C 3A-C前两条A —— B —— C已经把所有点连接起来了。这时候第三条A —— C不能再选。因为A → B → C → A形成了一个环。所以最小生成树不是“最小的边全部选。”而是“尽可能选择小边但是不能形成环。”这是我们的构造原则。四、一个非常重要的算法我们可以把问题变成把所有边按照权值从小到大排好然后一条一条尝试。例如A-B 1 B-C 2 A-C 3 C-D 4 B-D 5排序之后就是1 A-B 2 B-C 3 A-C 4 C-D 5 B-D然后看到 A-B ↓ 没有环 ↓ 选 看到 B-C ↓ 没有环 ↓ 选 看到 A-C ↓ 会形成环 ↓ 不选 看到 C-D ↓ 不会形成环 ↓ 选最后A —— B —— C —— D一共4 - 1 3条边结束这就是Kruskal 算法它的核心思想是按照权值从小到大的顺序选择 n−1 条边并保证这些边不构成回路。五、Kruskal 的最大难点怎么判断“会不会成环”这才是本课真正的重点。比如A —— B现在准备加入A —— C我们发现A、B已经属于一个集合。而C自己是一个集合。所以A-B-C不会形成环。但是如果现在准备加入A —— C而当前已经存在A —— B B —— C那么A |\ | \ B--CA 和 C已经连通。再加 A-CA → B → C → A就会产生环。因此我们真正需要解决的是两个点现在是不是已经属于同一个连通块六、这时候请出一个非常厉害的数据结构并查集英文叫Disjoint Set Union简称DSU中文一般叫并查集这个名字小学生第一次看到可能觉得很奇怪。其实非常简单并查集就是专门管理“谁和谁属于同一个朋友圈”的。七、用“朋友圈”理解并查集假设有1 2 3 4 5一开始大家互不认识{1} {2} {3} {4} {5}如果我们加入1 —— 2就变成{1,2} {3} {4} {5}再加入2 —— 3变成{1,2,3} {4} {5}再加入4 —— 5变成{1,2,3} {4,5}现在问1和3是不是一个朋友圈是。1和5是不是一个朋友圈不是。并查集最重要的就是解决他们是不是属于同一个集合以及把两个集合合并起来。八、并查集只有两个核心操作学生一定要记住① find(x)寻找x 属于哪个集合更准确地说找到 x 所在集合的“代表”。② merge(x,y)把x所在集合和y所在集合合并。九、最简单的并查集代码先看最基础版本int fa[1005]; int find(int x) { if (fa[x] x) return x; return find(fa[x]); }什么意思一开始for (int i 1; i n; i) fa[i] i;于是1 → 1 2 → 2 3 → 3 4 → 4 5 → 5每个人都是自己的老大。十、为什么fa[x]可以找到“老大”假设3 → 2 → 1也就是fa[3] 2 fa[2] 1 fa[1] 1那么find(3)过程find(3) ↓ fa[3] 2 ↓ find(2) ↓ fa[2] 1 ↓ find(1) ↓ fa[1] 1 ↓ 返回1所以find(3) 11就是这个集合的代表。十一、路径压缩让并查集跑得飞快刚才3 → 2 → 1如果我们执行find(3)可以顺便把它改成3 ─┐ 2 ─┼→ 1 1 ─┘也就是3 → 1 2 → 1 1 → 1以后再找 3find(3)一步就到了。这叫路径压缩代码写成int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); }这里最值得学生理解的是fa[x] find(fa[x]);它不是简单地“寻找”。而是寻找老大以后顺便让 x 直接认老大。十二、并查集如何判断“会不会形成环”这一步非常重要。假设现在有边u —— v我们先find(u) find(v)如果find(u) find(v)说明u 和 v 已经连通那么再连接u —— v就一定形成环。所以if (find(u) find(v)) { // 会成环 // 不能选 }反过来if (find(u) ! find(v)) { // 不会成环 // 可以选 }然后merge(u, v);把两个集合合并。十三、完整的 Kruskal 算法现在把前面的知识全部组合起来。首先定义一条边struct Edge { int u; int v; int w; };含义u —— v 权值 w例如Edge e; e.u 1; e.v 3; e.w 5;表示1 —— 3 费用5第一步按照权值排序sort(edge 1, edge m 1, cmp);比较函数bool cmp(Edge a, Edge b) { return a.w b.w; }意思权值小的边排在前面。第二步初始化并查集for (int i 1; i n; i) fa[i] i;第三步依次处理边for (int i 1; i m; i) { int u edge[i].u; int v edge[i].v; int w edge[i].w; if (find(u) ! find(v)) { merge(u, v); ans w; } }十四、完整模板这是值得大家掌握的Kruskal 最小生成树模板#include bits/stdc.h using namespace std; struct Edge { int u, v, w; }; Edge edge[200005]; int fa[100005]; bool cmp(Edge a, Edge b) { return a.w b.w; } int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); } void merge(int x, int y) { x find(x); y find(y); if (x ! y) fa[x] y; } int main() { int n, m; cin n m; for (int i 1; i n; i) fa[i] i; for (int i 1; i m; i) { cin edge[i].u edge[i].v edge[i].w; } sort(edge 1, edge m 1, cmp); int ans 0; int cnt 0; for (int i 1; i m; i) { int u edge[i].u; int v edge[i].v; int w edge[i].w; if (find(u) ! find(v)) { merge(u, v); ans w; cnt; } if (cnt n - 1) break; } cout ans endl; return 0; }十五、我们一起手算一次例如5个城市 1 —— 2 2 1 —— 3 5 2 —— 3 1 2 —— 4 4 3 —— 4 3 3 —— 5 6 4 —— 5 2首先排序边 权值 2 —— 3 1 1 —— 2 2 4 —— 5 2 3 —— 4 3 2 —— 4 4 1 —— 3 5 3 —— 5 6第1条2 —— 3没有连接{2} {3}所以选。费用ans 1第2条1 —— 2不同集合。选。{1,2,3}费用ans 1 2 3第3条4 —— 5不同集合。选。{1,2,3} {4,5}费用ans 5第4条3 —— 4两个集合不同。选。现在{1,2,3,4,5}费用ans 8已经选了n - 1 5 - 1 4条边结束。所以最小生成树总费用 8十六、这里有一个特别重要的“程序阅读题技巧”看到if (find(u) ! find(v))学生应该马上想到这是并查集。再看到sort(...)而排序关键字是w再看到ans w;那么很可能就是Kruskal 最小生成树这是 CSP-J 初赛程序阅读题非常值得培养的“代码识别能力”。十七、那么 Prim 又是什么如果说Kruskal 是“看边”。那么Prim 就是“看点”。我们对 Prim 的描述是从一个顶点开始不断寻找与当前顶点集合相邻、且代价最小的边把新的顶点加入集合直到所有顶点都加入。所以可以用一句特别容易记的话Kruskal边边边。Prim点点点。十八、Kruskal 和 Prim 到底有什么不同可以画成两幅图。Kruskal一开始A B C D E每个点都是独立的。然后不断加边 ↓ 加边 ↓ 加边 ↓ 加边最后A —— B —— C —— D —— E所以叫加边法Prim一开始选择A然后A ↓ A B ↓ A B C ↓ A B C D ↓ A B C D E不断把新点拉进来。所以叫加点法将二者总结为Kruskal 主要对边操作Prim 主要对顶点操作。十九、一个容易混淆的问题有学生会问最短路径和最小生成树是不是一回事不是这是必须讲清楚的。最短路径比如A → B → C问题是从 A 到 C哪条路线最短关注一个起点 → 一个终点典型算法Dijkstra BFS Floyd最小生成树问题是怎样把所有城市连起来并且总费用最低关注所有顶点典型算法Kruskal Prim所以最短路径解决“怎么走”。最小生成树解决“怎么把大家连起来”。这个区别大家要形成条件反射。二十、为什么 Kruskal 要排序我们已经讲过按照权值从小到大的顺序选择边。所以程序中sort(edge 1, edge m 1, cmp);是 Kruskal 的重要标志。时间主要花在排序如果有m 条边排序大约需要O(m log m)所以复杂度也是O(e log e)Kruskal 比较适合稀疏图。二十一、Prim 的特点Prim 不需要像 Kruskal 那样把所有边按照权值排序。它的思想是已有的点 ↓ 寻找连接外面的最小边 ↓ 加入一个新点 ↓ 继续它的复杂度是O(n²)它比较适合稠密图。二十二、CSP-J 初赛看到这些关键词要马上联想看到的关键词想到什么生成树树n个顶点n−1条边最小生成树总权值最小权值从小到大Kruskal加边法Kruskal加点法Prim判断是否成环并查集find(x)找集合代表fa[x]父节点sort 边很可能是 Kruskalfind(u)find(v)两点已经连通find(u)!find(v)可以考虑加边二十三、本课重要的“脑内步骤”看到一张图4 A -------- B | \ | 2| \5 |1 | \ | C -------- D 3Kruskal 的脑子里应该自动播放① 所有边排队 ② 最小边先来 ③ 问 “两个端点已经在一个朋友圈吗” ↓是 会成环 ↓ 不要 ↓否 不会成环 ↓ 要 ④ 两个朋友圈合并 ⑤ 选够 n-1 条 停止这其实就是整个 Kruskal。二十四、课堂练习练习1基础概念一个具有 8 个顶点的生成树有多少条边答案8 - 1 7练习2判断下面说法是否正确Kruskal 每次都选择当前最小的边因此不会产生环。错误。为什么因为Kruskal 选择最小边但还必须判断是否成环。练习3选择题最小生成树指的是A. 边数最少的树B. 顶点最少的树C. 所有生成树中权值和最小的树D. 任意一棵生成树答案C二十五、本课必须背下来的 8句话①树是一种没有环的连通图。②n 个顶点的树有 n−1 条边。③生成树包含原图的所有顶点。④最小生成树是所有生成树中权值和最小的那一棵。⑤Kruskal 加边法。⑥Prim 加点法。⑦Kruskal边按权值从小到大能加就加成环就跳过。⑧Kruskal 判断成环的好帮手并查集。二十六、给学生留下一个非常重要的算法思想其实Kruskal 最值得学习的并不仅仅是“会写一个模板”。它体现了一个非常重要的算法思想贪心算法每一次我们都想现在先选一条最便宜的边。这叫局部最优然后通过一个规则不能成环保证最后得到整体最优所以在后面的算法学习中学生应该逐渐形成这样的思维问题 ↓ 能不能每次做一个当前最好的选择 ↓ 这个选择会不会破坏最终答案 ↓ 如果不会 ↓ 贪心而 Kruskal 正是一个非常经典的贪心算法。课堂回顾第1部分理解 Kruskal1. 复习生成树 2. n-1条边 3. 最小生成树 4. 为什么不能只选最小边 5. Kruskal思想 6. 手工模拟 7. 贪心思想第2部分并查集 代码1. 为什么需要判断成环 2. 并查集的朋友圈模型 3. fa[] 4. find() 5. 路径压缩 6. merge() 7. Kruskal完整代码 8. 程序阅读题 9. Kruskal vs Prim