课前零食：只修够用的路

城市想全部连通，预算却嫌每条路都贵。今天的原则很克制：能让两个已经连通的地方再绕一圈的路，先别修；能把两块大陆第一次连起来的便宜路，很值得认真看一眼。

本节目标

学完后，你能：

说出生成树（spanning tree）为何有 $n-1$ 条边、为何不能有环；
从枚举所有连通边集的失败，推出按权排序、逐步合并连通块的 Kruskal 思路；
用“切开当前连通块”的交换想法理解割性质；
手动模拟并查集（Disjoint Set Union, DSU）的 find/union。

前置知识与课前自测

前置：无向带权图、排序、连通性。

一棵有 $n$ 个点的树为什么正好有 $n-1$ 条边？
已经有一条从 $A$ 到 $B$ 的路时，再加入直接边 $A-B$ 会产生什么结构？
若图不连通，是否存在一棵覆盖全部点的生成树？

答案

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。它不像是在“猜整棵树”，而是在慢慢把很多孤岛焊成一个整体。

步步式引导

1. 为什么“环”是可疑对象

若一套连通方案含一个环，删掉环上任意一条边，环的另外一侧仍让两端连通；所以至少有一条边是多余的。最优方案当然不会为纯粹的绕圈付钱，因而最小生成树一定无环。

反过来，只要当前森林的两端属于不同连通块，加入一条边不会形成环，并恰好把两个块并成一个。这个判定不需要真的画完整路径；DSU 维护每个点所属的代表元即可。

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$ 不会让总权变大。

这叫割性质。注意它说“至少存在一棵 MST 可选这条最轻边”；同权时树的形状可能不唯一，但最小总权不受影响。

核心知识：并查集只回答“是不是同一块”

DSU 的每个集合有一个根。find(x) 沿父亲指针找到根，并把路上节点直接挂到根（路径压缩）；union(a,b) 把较小的树挂到较大的树（按大小/秩合并）。它不保存具体路径，专职快速回答“两个点目前是否已经连通”。

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。直接回车会使用 5 个城市的预设图。每条边出现时，程序会打印两个端点所在分量、是否选中、若跳过则展示它闭合的环意图。

可以输入自己的 A-B-3,B-C-1 边表；先猜哪条边会因为“已经连通”被拒绝，再看 DSU 的回答。

扩展与联系

Prim 是从一个已选点集向外找最轻边，背后仍是割性质；“建超级源”可把建站费与连线费统一进一张图。正式课会讨论隐式完全图、替换边和 MST 边分类——它们都要求先把今天这个安全交换说清楚。

总结与自检

为什么 find(u)==find(v) 时加入边一定成环？
割性质的交换中，为什么环上一定存在一条能被替换的跨割边？
同权边会破坏最小总权的正确性吗？

自检答案

当前森林中已有 $u$ 到 $v$ 的路径；从 $S$ 出去又回到 $S$ 的环必须跨割偶数次；不会，只会使可选 MST 不唯一。

一周预热安排

第 1 天：手画一棵 5 点树，确认边数。
第 2 天：对一个环删不同边，观察连通性。
第 3 天：模拟 find/union 的父亲数组。
第 4 天：运行互动程序，记录每次跳过边的理由。
第 5 天：进入割性质与隐式完全图正式课。

00-课前零食-只修够用的路.md 11 KB History Raw