第3章 最小生成树
第 3 章 · 最小生成树
章节摘要：最小生成树（MST）问题要求在带权连通图中挑选"恰好连通全部顶点、边权总和最小"的边集。它是电网铺设、光缆布线、网络主干设计的数学模型，也是聚类分析（单链接聚类）的底层机制。本章先建立生成树的概念与切割性质等理论地基，再分别吃透 Prim 的"从一点长出来"与 Kruskal 的"从全局挑边"两条贪心路线（后者以并查集为左膀右臂），最后落到从基础设施到图像分割、基因组组装的应用全景。
你能学到什么
阅读完本章，你应当能够：
- 说明生成树"n 点 n 减 1 边且连通"的结构特征，以及生成树存在的前提；
- 陈述切割性质与环性质，并理解它们是两大算法正确性的共同来源；
- 模拟并实现 Prim 算法（含优先队列优化）与 Kruskal 算法（含并查集）；
- 按图的稠密度与边权分布选择 Prim 或 Kruskal；
- 把布线、聚类、图像分割等实际问题转译成最小生成树模型。
核心概念速览
最短路径关心"某两点怎么走"，生成树关心"大家怎么连"——前者是路径问题，后者是连通问题。
MST 章节知识地图
子章节导航
3.1 最小生成树：概念、性质与唯一性
先立地基：生成树长什么样、什么时候存在、切割性质为何成立、什么条件下 MST 唯一。
3.2 Prim 算法
"从一点开始长树"的贪心：每轮把横跨树内外的最小边吸进来。优先队列优化后适合稠密图。
3.3 Kruskal 算法与并查集
"全局排序、逐边尝试"的贪心：用并查集在近似常数时间里判断"加这条边会不会成环"。稀疏图首选。
3.4 最小生成树的应用
从电网布线的成本核算，到"删掉最长边自动得到聚类"的数据分析技巧，再到图像分割与基因组组装。
子章节之间的逻辑关系
3.1 的两个性质分别供养两个算法：切割性质说"横跨任何割的最小边安全"，Prim 每轮恰好应用一次它；环性质说"环上的最大边可弃"，Kruskal 排序后逐边裁决，用的正是它的逆否形式。
切割性质 ──支撑──> Prim 局部生长 ┐ ├──> 选型与工程实践 3.4 环性质 ──支撑──> Kruskal 全局挑边 ┘
理论（3.1）不先立住，两个算法就只是两段"碰巧正确"的代码；立住之后你会发现它们是同一条定理的两个投影。3.4 的应用反过来检验建模能力——同一套"最小连通"模型能覆盖从土木工程到生物信息学的广阔场景。
常见疑问解答
最小生成树和最短路径听起来像一回事，怎么区分？
一句话检验：问"从 A 到 B 怎么走最省"是最短路径；问"把所有点连通起来总代价最小"是最小生成树。两者的答案互不保证——树上两点间的路径常常不是两点的最短路，3.1 节有具体反例。把这句话写在你笔记的第一页，能省掉日后一大类建模错误。
学 MST 对进阶学习有什么用？
并查集是第一份红利——它在第 5 章是独立主角，在动态连通性、Kruskal 重构树等进阶主题里反复出场。第二份红利是"按边权层次思考图结构"的直觉：3.4 节的删边聚类、单链接等价性，展示了同一算法换个视角就是数据分析工具，这种"一鱼多吃"的思维方式比算法本身更值钱。
面试手写 MST，选 Prim 还是 Kruskal？
默认 Kruskal：排序加并查集，代码短、边界少、考官好验证。若题目明示"稠密图"或"边已按权组织"，再换 Prim。两手都要会，因为追问几乎必然是"另一个怎么写、什么时候更快"。
本章的自测清单
五题自查：说出生成树的边数特征及其论证；陈述切割性质并说明它是哪个算法的地基；写出一个支持双优化的并查集的 find；比较 Prim 与 Kruskal 的复杂度与适用形态；说明"删最长边聚类"为何等价于单链接聚类。五题过关，"最小连通"这个目标已经内化，下一章的管网在等你。
章末的一句提醒
MST 一章的算法最短、代码最少，但两个性质（切割与环）的证明味道最浓。别因为"代码好写"就跳过证明——后面无论是面试被追问"为什么贪心对"，还是自己设计新的贪心算法，这两份交换论证都是最常被复用的思维模板。写得短的东西，恰恰值得想得深。
前置知识与后续延伸
- 前置：第 1 章的连通性与无向图概念、邻接表与边集数组；2.1 节的优先队列用法（Prim 堆优化直接复用）。
- 为后续铺垫：3.3 的并查集是第 5 章数据结构专题的主角之一；最小生成树的"按边权层次揭示结构"思想，与第 4 章最大流最小割的"割"概念遥相呼应——两者都研究"切开图的最便宜方式"，只是目标不同。