3.1 最小生成树：概念、性质与唯一性

3.1 最小生成树：概念、性质与唯一性

本节摘要：生成树是连通无向图中"保持全部顶点连通且无环"的边子集，恰好含"顶点数减一"条边；最小生成树是边权总和最小的那棵。本节建立生成树的结构特征、存在条件、两种等价刻画（切割性质与环性质），并讨论唯一性问题——边权互不相同时 MST 唯一，否则可能有多解。这两个性质分别是 Prim 与 Kruskal 正确性的理论地基。

本节导航

阅读完本节，你应当能够：

1. 给出生成树的定义并证明"n 顶点恰有 n 减 1 条边"；
2. 陈述切割性质与环性质，并用交换论证说明它们成立；
3. 判断一个给定图是否存在生成树、MST 是否唯一；
4. 说明两个性质与两大算法的对应关系。

一、问题与直觉：连通，但一分钱不多花

设想你负责一个新居民区的电网：每个住户都要通电，电线可以沿任意两户之间铺设且造价已知。直觉告诉你，最优方案里不该有环——有环意味着其中一条线是冗余的，剪掉它仍然保持人人通电，还能省一笔钱。也不该有"孤岛"——那等于有人没电。

把住户看作顶点、候选线路看作带权边，最优方案就是一个"连通所有顶点、无环、边权总和最小"的边子集——这正是最小生成树的定义。注意它与最短路径的分野：MST 不关心"从 A 到 B 走哪条路最省"，只关心"整体连通的总造价"；事实上，MST 上两点间的路径常常不是它们的最短路径，两套优化目标互不包含。

先明确生成树的定义：连通图 G 的生成树是 G 的一个子图，包含 G 的全部顶点、保持连通、且不含环。

二、生成树的结构特征

边数定理：n 个顶点的生成树恰好含 n 减 1 条边。论证：从单点开始，每并入一条边就把一个新顶点拉进连通块——n 个点需要 n 减 1 次并入；同时，任何时刻"点数减边数恰为 1"这个量在加边时不变，若加了第 n 条边，多出的边必然与已有边构成环。反过来，"n 点、n 减 1 边、连通"三者联立也必然无环——这组等价刻画是校验算法输出的快捷方式。

存在性：当且仅当图连通。图不连通时没有生成树，只有生成森林——每个连通分量各有一棵生成树。工程上要提前检查：先跑一遍 DFS 数连通分量（第 1 章 1.3 的技能），分量数大于 1 就直接报告"无法全量连通"，或退而求各分量分别求 MST。

数量级：完全图的生成树个数是 n 的 n 减 2 次方（Cayley 公式），爆炸式增长——这正是"贪心直接构造"比"枚举比较"聪明的地方：Prim 和 Kruskal 都绕开了指数级的搜索空间。

生成树 vs 图 vs 森林

三、两个核心性质：贪心的通行证

切割性质（Prim 的地基）

割：把顶点集切成两个不相交子集。一条边"横跨割"指它的两端分属两侧。

陈述：设 e 是横跨某个割的所有边中权重最小的，那么存在一棵 MST 包含 e。

交换论证：任取一棵不含 e 的 MST，加入 e 后形成唯一的环，环上必有另一条横跨同一割的边 f；用 e 换掉 f，仍保持连通、边数不变、无环，而权重不增（e 不大于 f）——得到一棵不更贵的生成树。若所有横跨割的最小边唯一，则 e 必属于每一棵 MST。

环性质（Kruskal 的地基）

陈述：图任何环上权重最大的边（若唯一最大），必然不属于任何 MST。

论证同款：把这条最大边删掉，环断成两截，用环上其他边已能保持端点连通，再按需补边只会更省。

这两个性质合起来是一句话："横跨两半的最小边安全；环上的最大边可弃"。Prim 每轮把"树内 vs 树外"当作割、吸入横跨最小边，是把切割性质用成了算法；Kruskal 按权升序逐边尝试、只在"两端尚不连通"时并入，等于在全局尺度上反复应用环性质。正确性不是玄学，全部写在 3.1 这一节里。

四、唯一性与多解

唯一性定理：若图中所有边权互不相同，则 MST 唯一。反证：若有 两棵不同的 MST，考察其对称差中权重最小的边 e（属于 T1 不属于 T2），把 e 加进 T2 成环，环上必有 T1 没有的边 f，且由 e 的最小性知 e 的权小于 f 的权，用 e 换 f 得到更便宜的生成树，与 T2 最小矛盾。

反过来，边权重复时 MST 可以不唯一：三点两两连边、权全为 1，任取两条边都是 MST。此时不必焦虑——多解只是"总造价相同的多种方案"，业务上可按次级标准（如施工难度、拓扑偏好）挑一个。算法输出哪棵取决于实现细节（排序稳定性、起点的选择），都是合法答案。

例：三顶点三角形 各边权均为1
  任取两条边都是MST 共三棵 总造价均为2
例：边权互异 2 4 8 1 7 3 11 6 2 4 14 10 的经典9点图
  MST唯一 且首条入选边必为权重1的那条
​

⚠️ 常见坑：把"两点在 MST 中的路径"当成"两点的最短路径"。一个干净的反例：四点 A、B、C、D，边 A 到 B 权 1、B 到 C 权 1、C 到 D 权 1、A 到 D 权 2.5。MST 选三条权 1 的边，A 到 D 在树上要走 3；而最短路径是直连的 2.5，MST 根本没有选它。两套目标独立，答案互不保证——需要最短路径就回第 2 章的算法，需要最小连通就留在本章。

💡 关键直觉：切割性质是"安全证书"——只要你手里这条边是某个割的横跨最小边，加它永远不会错。Prim 和 Kruskal 的全部智慧，就是把"构造合适的割、找到横跨最小边"这件事做到高效。

五、深入一层：从 MST 到"次优"与"瓶颈"

两个延伸概念在面试与工程中都高频出现。次小生成树：严格大于 MST 的最小生成树。求法通常是"枚举非树边替换"——对每条不在 MST 里的边，找出树上两端点路径上的最大边，替换后得到一棵新树，取总权最小者。它回答的问题是"最优方案不可行时（某条边施工受阻），备选方案贵多少"。

最小瓶颈生成树：让"树中最长边"最小的生成树。一个简洁的事实是：MST 必然也是最小瓶颈生成树——Kruskal 按权升序选边，最后入选的边就是树中最长的边之一，且贪心保证了它尽可能小。注意反向不成立（最小瓶颈树不必是 MST）。瓶颈视角的应用包括：网络中"任意两点间最差链路最优"的保障问题。

交换论证也值得再强调一遍方法论价值：它是贪心算法证明的万能模板——假设最优解不含贪心的选择，构造出"换入贪心选择后不更差"的新解，导出矛盾。3.2 与 3.3 的正确性、本节的两个性质、乃至许多调度类贪心，用的都是这一套推理。掌握模板，比记住结论更耐用。

常见疑问解答

MST 的"最小"是总边权最小，那"平均"或"最大边"最小呢？

它们是不同的问题。总权最小是 MST；最大边最小是最小瓶颈生成树（MST 顺带达成）；平均权最小在总权与边数固定时等价于总权最小，但若允许边数变化则又不同。拿到需求先问清楚"优化的到底是哪个量"，再选模型——这比背十个算法名有用。

有向图有"最小生成树"吗？

标准 MST 定义在无向图上。有向图的对应物是"最小树形图"（以指定根可达全部点、边权和最小的弧集），经典解法是朱-刘与 Edmonds 算法，使用频率更小众。多数业务（布线、组网）本质无向，先确认方向语义再决定是否需要树形图。

边权是小数时，唯一性与实现有影响吗？

唯一性结论不变（互异即可），但浮点比较会带来实现噪声：并列权重在浮点下可能"看起来互异"，多解与舍入误差叠加。工程惯例是把权乘以精度倍数转整数，或用容差比较；对唯一性敏感的业务（分账、审计），转整数是更稳妥的选择。

不连通的图怎么"尽量"连通？

先跑连通分量，每个分量内求 MST，得生成森林；若必须全图连通，"跨分量连边"的成本问题本质是"在分量收缩后的图上再做一次 MST"——两层贪心嵌套，思路一致。

动手实验：四个顶点穷举验证切割性质

取四个顶点的带权完全图（六条边权取 1 到 6 的不同排列），写一个十行的小程序：枚举所有生成树（四点图只有 16 棵），找出最小总权；再对每个可能的割（三个非平凡割）验证"横跨最小边确实出现在某棵 MST 中"。换几组权重（含并列）重复，观察唯一性与多解的边界。这个一小时的实验把本节所有定理从"书上的话"变成"自己数出来的事实"——许多读者反馈，做完这个实验后才真正"信"了贪心算法。

性质的记忆锚点

两个性质可以用同一句话锚定："局部最优的替换永不变贵"。切割性质说"换入横跨最小边不贵"，环性质说"踢掉环上最大边不亏"——一进一出一句话。考试或面试时先默念这句话，再展开成正式陈述，比死记两条命题稳得多。

生成树和生成森林在代码里怎么区分？

看结果边数：恰为"点数减一"且连通，是生成树；少于它则说明图不连通，结果按连通分量各自成树，构成生成森林。实现层面的惯例是让算法自然产出（Kruskal 扫完全部边即停），再事后用边数与覆盖点数做断言分类——把"结构判定"留到输出校验阶段，主流程保持简单。

再补一条术语对照：生成树的英文是 spanning tree，最小生成树是 minimum spanning tree，文献里常缩写为 MST；生成森林是 spanning forest。后续阅读论文或英文文档时，认得这三个词就能直接对上本节的概念。

一节小结

• 生成树定义：含全部顶点、连通、无环的子图；恰好"顶点数减一"条边。
• 存在条件：图连通；否则只能得到生成森林（每分量一棵树）。
• 规模提示：完全图有 n 的 n 减 2 次方棵生成树，枚举不可行，贪心是唯一务实路线。
• 切割性质：横跨任意割的最小边安全，可放心加入 MST——Prim 的地基。
• 环性质：环上（唯一）最大边可弃——Kruskal 的地基。
• 唯一性：边权互异则 MST 唯一；有权重并列时可能多解，总造价相同，按次级标准取舍即可。
• 与最短路的关系：MST 优化"总连通代价"，不保证树上路径最短，两套目标互不包含。

地基打好，下一节先上 Prim——从一粒种子开始，看树怎么"长"出最小总造价。