Prim 算法 vs Kruskal 算法
作者：野牛程序员：2025-12-05 10:28:42算法阅读 2205
Prim 算法 vs Kruskal 算法
Prim 算法 vs Kruskal 算法
（最小生成树 MST 两大核心算法对照）
1. 思想对比
| 算法 | 核心思想 |
|---|---|
| Prim | 从一个顶点开始，不断选择与当前生成树连接的最小权值边，逐步扩大树。 |
| Kruskal | 从所有边中按权值排序，从最小边开始，只要不成环就加入生成树。 |
2. 输入数据结构偏好
| 情况 | 更适合 |
|---|---|
| 稠密图（边多） | Prim（邻接矩阵实现）效率高 |
| 稀疏图（边少） | Kruskal（排序 + 并查集）更快 |
3. 时间复杂度对比
| 实现方式 | Prim | Kruskal |
|---|---|---|
| 邻接矩阵 | O(V²) | — |
| 优先队列 + 邻接表 | O(E log V) | — |
| 排序边列表 | — | O(E log E) ≈ O(E log V) |
结论：
→ 稀疏图中 Kruskal 更快
→ 稠密图中 Prim（堆优化版）或矩阵版更稳定
4. 数据结构需求对比
| 需求 | Prim | Kruskal |
|---|---|---|
| 优先队列 | 常用（堆优化） | 不需要 |
| 并查集 | 不需要 | 必须，用于判断是否成环 |
| 图结构 | 邻接矩阵或邻接表 | 边列表（Edge List） |
5. 是否依赖起点？
| 算法 | 是否需要指定起点 |
|---|---|
| Prim | ✔ 需要 |
| Kruskal | ✖ 不需要 |
6. 工作流程差异
Prim 扩展方式：
像往水中投石子，从起点向外一圈圈扩散：
起点 → 最小边 → 扩展到新节点 → 再从所有可选边中选最小
Kruskal 扩展方式：
像给所有边从小到大排队，只要不成环就接入：
最小边 → 第二小边 → 第三小边 → ...
7. 核心区别总结（最关键）
| 类别 | Prim | Kruskal |
|---|---|---|
| 扩展方式 | 从点开始扩展 | 从边开始扩展 |
| 是否成环检查 | 不需要 | 必须使用并查集 |
| 适用图类型 | 稠密图 | 稀疏图 |
| 实现复杂度 | 稍复杂（堆 + 邻接表） | 简单（排序 + 并查集） |
8. 一句话记忆
Prim：像建房，从一个房间开始一直扩展
Kruskal：像选木材，先把所有木头从短到长排队，不会重复就拿走
野牛程序员教少儿编程与信息学奥赛-微信|电话：15892516892
