最小生成树
本节目标
用切分性质构造连接无向图全部顶点且边权和最小的树，掌握 Kruskal 与 Prim。
最小生成树（MST）在无向连通带权图中选出 n - 1 条边，连接所有顶点且总权值最小。它不指定起点和终点，目标是让整张图连通；若图不连通，就不存在生成树。
识别信号
- 要把全部节点连通，且总代价是所选边的总和。
- 每条边只需决定选或不选，要求没有环并最终连通。
- 边已显式给出且方便排序：考虑 Kruskal。
- 图由点的距离隐式定义，或可从一个点向外扩张：考虑 Prim。
问题模型与核心不变量
核心依据是切分性质：把顶点分成两个非空集合时，跨越这条切分的最轻边，存在于某棵最小生成树中。若一棵最优树没有它，加入这条更轻边会形成环；环上必有另一条跨越同一切分的边，删去它不会断连且不会更重。
Kruskal 从小到大看边，维护已选边形成的若干连通块。连接不同连通块的当前最轻边跨越某个块与其余顶点的切分，因而安全；连接同一块的边会成环，必须跳过。Prim 维护已加入顶点集合与每个外部点连接到该集合的最小边，每轮选最小者，同样是切分性质的直接应用。
通用模板
Kruskal：边按权值排序
依次尝试每条边：若两端不连通，选边、合并连通块、累计权值
选边数等于 n - 1 才成功
Prim：任选一点，minDist[start] = 0
每轮选择未加入点中 minDist 最小者，累加它
用该点到其余点的边更新 minDist
Kruskal 的“是否连通、如何合并”直接使用8.3 连通性、并查集与二分图中已经建立的并查集操作约定；这里不重复其完整实现教程。
模板变体
- Kruskal：显式边排序，时间主要是
O(m log m)；适合边列表输入。 - Prim：邻接矩阵或按需计算边权，朴素实现为
O(n²)；适合完全图和点集距离。 - 任一算法选中不足
n - 1条边，都说明原图不连通。
母题序列
按必学顺序练习：
- Kruskal 算法求最小生成树（必学）：排序边并只接纳连接不同连通块的边。
- 连接所有点的最小费用（必学）：在完全图上按需计算曼哈顿距离执行 Prim。
常见误区
- 把最短路的“从起点距离”误当作 MST 的目标；两者优化对象不同。
- 见到小边就选而不检查是否成环。
- Kruskal 未检查选边数，给不连通图错误地返回森林权值。
- Prim 更新的是点到已选集合的最小边，不是从固定起点的路径和。
- 为完全图显式生成全部边，造成不必要的
O(n²)边存储。
迁移方向
新题先验证它要求的是“全体连通的最小总边权”而非最短路。输入给出边表时，从 Kruskal 的排序和连通块不变量出发；点间代价可即时计算时，从 Prim 的 minDist 出发。若出现额外约束（必须/禁止边、第二小生成树等），仍先用切分性质判断哪类选边可以安全保留。