什么是最小生成树？Prim 和 Kruskal 算法有什么区别？
简化版
最小生成树（MST）是连通所有顶点、总权重最小、且无环的边的集合（n 个点用 n-1 条边把所有点连起来，权重和最小）。两种贪心算法：Prim ——从一个点出发，每次加「连接已选集合与外部的最小权边」，用优先队列，适合稠密图；Kruskal ——把所有边按权排序，从小到大加，用并查集跳过会成环的边，适合稀疏图。
详细版
MST 的定义：给一个带权连通无向图，选出 n-1 条边，把所有 n 个顶点连成一棵树（连通、无环），使这些边的权重总和最小。
Prim（从点扩展）
1. 任选一个起点，加入"已选集合"
2. 每次从"连接已选集合和未选点的所有边"里，挑权重最小的
3. 把这条边和它连接的新点加入集合
4. 重复直到所有点都在集合里（选了 n-1 条边）用优先队列维护候选边，O(E log V)。
Kruskal（从边扩展）
1. 把所有边按权重从小到大排序
2. 依次考虑每条边：如果它的两个端点不在同一连通块（用并查集判断），就选它、合并两块
3. 如果两端已连通（选它会成环），跳过
4. 选够 n-1 条边就完成用并查集判环，O(E log E)。
完整版教学
一、MST 解决什么问题
「用最小的成本把所有点连起来」——修路连通所有城市、布线连通所有机房、管网覆盖所有小区，都是 MST。它要求：连通（所有点可达）、无环（环里有多余的边，去掉最贵的仍连通）、权重最小。n 个点的生成树恰好 n-1 条边，MST 就是所有生成树里权重和最小的那棵。
二、两种算法都是贪心，但角度不同
Prim 和 Kruskal 都基于「贪心选最小边」，但一个从点长、一个从边选：
- Prim「以点扩展」：维护一个不断长大的连通块，每次贪心地把「块外最近的点」拉进来。像滚雪球。
- Kruskal「以边选择」：把所有边从小到大排队，能不成环就选。像逐条挑选便宜的边拼起来。
两者都能得到正确的 MST（贪心的正确性由「切分定理/cut property」保证：跨越任意切分的最小边一定属于某棵 MST）。
三、Prim 的实现要点
- 用一个
dist[]或优先队列记录「每个未选点到已选集合的最小边权」。 - 每次取出最小的点加入集合，然后用它更新邻居的
dist。 - 结构和 Dijkstra 非常像（都是「优先队列 + 松弛」），区别是 Prim 松弛的是「到集合的边权」，Dijkstra 松弛的是「到起点的路径和」。
- 复杂度 O(E log V)（二叉堆），邻接矩阵朴素版 O(V²) 适合稠密图。
四、Kruskal 的实现要点
- 先把所有边排序（这是主要开销，O(E log E)）。
- 用并查集高效判断「加这条边会不会成环」：两端
find相同就成环、跳过；否则union合并。 - 因为主要靠边排序 + 并查集，边越少越快，适合稀疏图。
五、Prim vs Kruskal 怎么选
| Prim | Kruskal | |
|---|---|---|
| 思路 | 从点扩展（滚雪球） | 从边选择（排序） |
| 核心结构 | 优先队列 | 排序 + 并查集 |
| 复杂度 | O(E log V) | O(E log E) |
| 适合 | 稠密图（边多） | 稀疏图（边少） |
- 稠密图（E 接近 V²） → Prim（尤其邻接矩阵朴素版 O(V²)）。
- 稀疏图（E 少） → Kruskal（边少排序快）。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| MST 定义 | 连接所有点且总权重最小的无环边集 |
| Prim | 从点集向外扩展，每次选跨割最小边 |
| Kruskal | 按边权从小到大选，不成环就加入 |
Kruskal:
sort edges by weight
for edge in edges:
if find(u) != find(v):
union(u, v)
add edgePrim 像从一个岛扩张，Kruskal 像从全局最便宜的边开始拼森林。
- 误区：最小生成树适用于有向图。 经典 MST 定义在连通无向带权图上；有向图对应的是最小树形图等不同问题。
- 误区：MST 一定唯一。 边权有相等时可能存在多棵总权重相同的最小生成树。
- 误区：Kruskal 选最小边不需要判环。 不判环会形成环，结果就不是树；并查集用于快速判环。
- 追问：Prim 适合什么图？ 配合邻接矩阵常用于稠密图，配合堆和邻接表也可处理稀疏图。
- 追问：Kruskal 适合什么图？ 边集排序清晰，通常适合稀疏图或边列表输入。
- 追问：复杂度怎么比较？ Kruskal 主要是排序 O(E log E)，Prim 取决于矩阵或堆实现。
七、加强记忆
最小生成树（MST）= 连通所有点、无环、n-1 条边、权重和最小的边集。两种贪心：Prim「从点滚雪球」——优先队列每次拉入「块外最近的点」，像 Dijkstra，适合稠密图，O(E log V)；Kruskal「从边挑选」——边按权排序、并查集判环跳过成环边，适合稀疏图，O(E log E)。稠密用 Prim、稀疏用 Kruskal，正确性由切分定理保证。