# 课前零食：只修够用的路 > 城市想全部连通，预算却嫌每条路都贵。今天的原则很克制：能让两个已经连通的地方再绕一圈的路，先别修；能把两块大陆第一次连起来的便宜路，很值得认真看一眼。 ## 本节目标 学完后，你能： - 说出生成树（spanning tree）为何有 $n-1$ 条边、为何不能有环； - 从枚举所有连通边集的失败，推出按权排序、逐步合并连通块的 Kruskal 思路； - 用“切开当前连通块”的交换想法理解割性质； - 手动模拟并查集（Disjoint Set Union, DSU）的 `find/union`。 ## 前置知识与课前自测 前置：无向带权图、排序、连通性。 1. 一棵有 $n$ 个点的树为什么正好有 $n-1$ 条边？ 2. 已经有一条从 $A$ 到 $B$ 的路时，再加入直接边 $A-B$ 会产生什么结构？ 3. 若图不连通，是否存在一棵覆盖全部点的生成树？
答案 1. 从一个点开始，每加一条不成环的边最多新接入一个点，要接入其余 $n-1$ 个点恰需这么多边。2. 一个环。3. 不存在；此时只能谈每个连通块各自的最小生成森林。
## 互动规则：每条路先问“它连起了什么”，再问“它多贵” 请把边写成卡片 `(端点,价格)`，把每个当前连通块圈成一个泡泡。每翻一张边卡，都在纸上回答四件事：`它两端在哪两个泡泡`、`加它会不会闭环`、`若加入泡泡如何合并`、`为什么可以暂时相信这条边`。不要一上来就把边按算法名分类。 今天的目标是亲自搭出“森林 → 连通块 → 割 → 安全边”的框架；并查集只是这份账本的高效记事员。 ## 从零搭框架：先删掉显然多余的路 ### 第 0 步：从一张小图枚举“够用的连通方案” 画四个点和五条无向边：`A-B(1), A-C(2), B-C(3), C-D(2), B-D(4)`。先不要排序；任选几组边，检查它们是否让所有点连通。每组都数一数边数和是否含环。 > 停顿 0：若一个连通方案有 4 个点却选了 4 条边，它一定含环吗？删掉环上一条边后，连通性为什么不会消失？
展开：生成树先来自“去掉冗余” 4 点连通无环只需 3 条边；连通图多出一条边就形成环。环上任意一条边的两端还可沿环另一侧相连，所以至少有一条路不是维持连通的必需品。最小生成树不可能为纯绕圈的冗余边付钱。
### 第 1 步：让“当前已经连好”成为状态 从四个单点泡泡 `{A},{B},{C},{D}` 开始，按价格查看边卡。先看 `A-B(1)`：它连接两个不同泡泡；再看 `A-C(2)`；随后看 `C-D(2)`；最后再看 `B-C(3)`。 请填： | 正在看的边 | 两端当前泡泡 | 加入/跳过 | 加入后泡泡 | 理由 | |---|---|---|---|---| | A-B(1) | | | | | | A-C(2) | | | | | | C-D(2) | | | | | | B-C(3) | | | | | > 停顿 1：到 `B-C(3)` 时，为什么不需要真的在图上 DFS 寻路，也能知道它会成环？
展开：森林状态足够回答环问题 前三条边后四点已经在同一泡泡；B、C 属于同一连通块意味着当前森林已有 B 到 C 的唯一树路径，加入 `B-C` 会闭合环。我们只需维护“代表元是否相同”，这正是 DSU 的问题。
### 第 2 步：为什么可以先看便宜边，而不是贪心碰运气 把当前泡泡 $S={A,B}$ 用一条虚线和外界隔开。跨线边有 `A-C(2), B-C(3), B-D(4)`。请先选择最轻跨线边；再假设某棵最优树没有它，沿那棵树从 S 走向外部时，找第一条跨虚线的边。 > 停顿 2：把最轻边加进那棵最优树后为什么出现环？环上为什么一定有另一条跨虚线的边可以删？
展开：割性质是可见的交换 加新边把两端接通，旧树中原本两端已有路径，故出现环；从 S 出去又回到 S 的环必须跨割至少两次，所以有另一条跨割边。新边不重于它，替换后仍不更贵。于是至少存在一棵最优树包含当前最轻跨割边；这不是“便宜看着顺眼”，而是可交换的证据。
### 第 3 步：先手写并查集的最小版本 给 `A,B,C,D` 各写一个 `parent`，初始都指向自己。依序 `union(A,B)`,`union(A,C)`,`union(C,D)`，每步跟父亲指针到根。然后再做 `find(B),find(C)`。 > 停顿 3：`find` 的返回值到底代表一条路径，还是一个集合的名字？路径压缩改的是正确性还是让下次更快？
展开：DSU 不知道树形路线，只知道同一泡泡 根是集合代表，不是原图中的“父边”。路径压缩把查找路上的点直接连到根，不改变哪些点在同一集合，只减少未来追父亲的长度。按大小合并与路径压缩让大量查询近似常数摊还。
### 第 4 步：把框架写成一句可执行的话 请补全：`状态是 ______；候选按 ______ 顺序来；若两端 ______ 就选；选后 ______；停止条件是 ______。`
展开：Kruskal 的真正骨架 状态是当前森林/连通块；候选按权从小到大；两端在不同集合就选；选后合并集合；选够 $n-1$ 条边或候选耗尽。排序解决“先看谁”，DSU 解决“它是否闭环”，割性质解决“为什么可以选”。
## 问题动机：把所有选路方案列出来不现实 一张图有 $m$ 条边，枚举“选或不选”已有 $2^m$ 种子集；还要逐份检查是否连通、是否无环。我们需要一种不回头的大原则：每次只看一条当前最便宜的边，若它连接两个不同连通块，就加入；若两端早已在同一块，加入只会造环，跳过。 ![Kruskal 按权从小到大选边](../插图/06-最小与最大生成树/00-MST-01-Kruskal.svg) 这就是 Kruskal。它不像是在“猜整棵树”，而是在慢慢把很多孤岛焊成一个整体。 ## 步步式引导 ### 1. 为什么“环”是可疑对象 若一套连通方案含一个环，删掉环上任意一条边，环的另外一侧仍让两端连通；所以至少有一条边是多余的。最优方案当然不会为纯粹的绕圈付钱，因而最小生成树一定无环。 反过来，只要当前森林的两端属于不同连通块，加入一条边不会形成环，并恰好把两个块并成一个。这个判定不需要真的画完整路径；DSU 维护每个点所属的代表元即可。 ```text sort edges by weight ascending for (u, v, w) in edges: if find(u) != find(v): choose (u, v, w) union(u, v) else: skip it # 它会在当前森林中闭合一个环 stop after choosing n - 1 edges ``` ### 2. 最便宜的跨块边为什么安全 把某个当前连通块 $S$ 和外面切开。Kruskal 正在看的边 $e$ 是尚未考虑边中最轻、又跨过这个割的一条。取任意一棵最小生成树：若它已有 $e$，很好；若没有，加入 $e$ 会出现一个环，环上必有另一条也跨这个割的边 $f$。因为 $e$ 不比 $f$ 重，删 $f$ 换 $e$ 不会让总权变大。 ![割上的便宜边可替换较贵边](../插图/06-最小与最大生成树/00-MST-02-割性质.svg) 这叫割性质。注意它说“至少存在一棵 MST 可选这条最轻边”；同权时树的形状可能不唯一，但最小总权不受影响。 ## 核心知识：并查集只回答“是不是同一块” DSU 的每个集合有一个根。`find(x)` 沿父亲指针找到根，并把路上节点直接挂到根（路径压缩）；`union(a,b)` 把较小的树挂到较大的树（按大小/秩合并）。它不保存具体路径，专职快速回答“两个点目前是否已经连通”。 ```text find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] union(a, b): ra, rb = find(a), find(b) if ra == rb: return false attach smaller root below larger root return true ``` ## 纸上模拟：把一条边从候选变成证据 对边表 `A-B(1),D-E(1),A-C(2),C-D(2),B-C(3),B-D(4),C-E(5)`，画五个单点泡泡，按权执行： | 边 | `find(u),find(v)` | 选/跳 | 当前已选边 | 分量 | |---|---|---|---|---| | A-B(1) | | | | | | D-E(1) | | | | | | A-C(2) | | | | | | C-D(2) | | | | | | B-C(3) | | | | |
展开：先选够，再拒绝剩余环边 前四条分别把 `{A,B}`、`{D,E}`、`{A,B,C}`、`{A,B,C,D,E}` 合并，已选 4 条边，正好是 5 点树所需数目。`B-C` 的两个 `find` 已相同，跳过。请注意“已连通”是跳过理由；“它价格更贵”本身不是逻辑理由。
排序是 $O(m\log m)$，DSU 的总工作近似 $O(m\alpha(n))$，其中 $\alpha$ 小得像竞赛时限里的一粒芝麻；所以整体由排序主导。 ## 实现指南 - 边权、答案和排序对象分开保存；答案可能超出 `int`。 - 处理同权边时，基础求总权可以任意顺序；若题目问“某边是否必在每棵 MST”，要留到正式课的同权批处理。 - 选边数不足 $n-1$ 说明原图不连通；不要输出一棵假装覆盖全图的树。 - 最大生成树只需把排序改为从大到小，安全性证明完全对称。 ## 互动小实验室 运行 [只修够用的路.py](../../互动程序/06-最小与最大生成树/00-只修够用的路.py)。直接回车会使用 5 个城市的预设图。每条边出现时，程序会打印两个端点所在分量、是否选中、若跳过则展示它闭合的环意图。 可以输入自己的 `A-B-3,B-C-1` 边表；先猜哪条边会因为“已经连通”被拒绝，再看 DSU 的回答。 ## 扩展与联系 Prim 是从一个已选点集向外找最轻边，背后仍是割性质；“建超级源”可把建站费与连线费统一进一张图。正式课会讨论隐式完全图、替换边和 MST 边分类——它们都要求先把今天这个安全交换说清楚。 ## 总结与自检 1. 为什么 `find(u)==find(v)` 时加入边一定成环？ 2. 割性质的交换中，为什么环上一定存在一条能被替换的跨割边？ 3. 同权边会破坏最小总权的正确性吗？
自检答案 当前森林中已有 $u$ 到 $v$ 的路径；从 $S$ 出去又回到 $S$ 的环必须跨割偶数次；不会，只会使可选 MST 不唯一。
## 一周预热安排 - 第 1 天：手画一棵 5 点树，确认边数。 - 第 2 天：对一个环删不同边，观察连通性。 - 第 3 天：模拟 `find/union` 的父亲数组。 - 第 4 天：运行互动程序，记录每次跳过边的理由。 - 第 5 天：进入[割性质与隐式完全图正式课](01-割性质与隐式完全图建模.md)。