最小生成树算法
最小生成树（Minimum Spanning Tree, MST）是连通无向带权图上的一棵总边权最小的生成树——它从原图挑出恰好 n−1 条边把 n 个顶点连通成无环结构，且这些边权之和在所有可能里最小。它是网络设计的数学模型（用最低成本把一群节点连通起来），也是贪心算法最经典的成功范例：Kruskal 与 Prim 两种算法都基于「安全边（safe edge）」定理——只要每次都选一条不构成环且权最小的边加入，最终一定得到 MST，无需回溯。
两者思路截然不同：Kruskal（按边权排序，逐条尝试加入，用并查集判环）像「全局挑最便宜的边」，复杂度 O(E log E)，与点数无关、对稀疏图友好；Prim（从任一顶点出发，每次选一条「连已选集合」的最小边，用最小堆优化）像「从一点向外长成一棵树」，复杂度 O(E log V)，对稠密图（邻接矩阵朴素版 O(V²)）更稳。选型口诀一句话：稀疏选 Kruskal，稠密选 Prim。当所有边权唯一时两者得到的边集合完全相同；存在相等边权时 MST 可能不唯一，但总权值必然相同。
评价
优点
- 正确性有保证：两者都基于「MST 的安全边 / 切割性质 / 环性质」可严格证明，每步贪心选边无需回溯，保证全局最优——是贪心算法少数「次次局部最优 = 全局最优」的范例
- 实现成熟、常数小：Kruskal = 排序 + 并查集；Prim = 堆 + 松弛，两者都建立在通用组件上，几十行即可落地，竞赛/面试高频
- 适用面互补：Kruskal 对稀疏图（边少排序快）占优，Prim 对稠密图（邻接矩阵朴素 O(V²) 不依赖 E）占优——总能挑出更优的那一个
缺点
- 仅限连通无向带权图：图不连通时只能求出最小生成森林（每个连通分量一棵）；负权边虽然不影响 MST 定义，但要小心「负权≠最短路」的混淆
- MST 可能不唯一：边权存在相同时，可能有多棵总权相同的最小生成树——题目问「唯一性」时要靠相等权值边是否构成环来判定
- 不支持有向图：有向图的对应问题是最小树形图（朱-刘算法），不是本叶范围，初学者易混
本叶地图
- 入门 —— 生成树与 MST 定义、n−1 条边无环连通、切割性质与环性质、Kruskal 与 Prim 两种贪心思路对比、稀疏/稠密选型
- Kruskal 与 Prim：两种贪心策略 —— Kruskal（排序边 + 并查集判环，O(E log E)）、Prim（从点出发贪心最小边，堆优化 O(E log V)）、代码实现、复杂度对比
- 选型与应用场景 —— 稀疏选 Kruskal、稠密选 Prim、MST 唯一性、应用（网络设计/聚类/近似 TSP）
- 参考 —— 复杂度对比表、Kruskal/Prim 代码模板、选型决策、易错点（判环/堆优化/重边）、权威链接
交互演示
- Kruskal 可视化演示 —— 按边权排序逐条加入，并查集判环
- Prim 可视化演示 —— 从一点出发，堆选最小连边