Prim 算法和 Kruskal 算法都是求解图的最小生成树（MST）的经典贪心算法，但它们在核心策略和适用场景上有显著区别：
1. 核心思想与操作对象
- Prim 算法（加点法）：
- 思想：从图中任意一个节点开始，每次选择与当前已构建生成树距离最近（权值最小）的一个节点及其相连的边，加入到生成树中。
- 操作对象：以顶点为中心，像“生长”一样从一点扩散到整个图。
- Kruskal 算法（加边法）：
- 思想：将图中所有的边按权值从小到大排序，每次选择权值最小且不会与已选边形成环的边，加入到生成树中。
- 操作对象：以边为中心，在任意时刻可能产生多个不连通的分支（森林），最终合并为一棵树。 [1, 2, 3, 4, 5, 6]
2. 关键区别对比
| 特性 [1, 4, 5, 6, 7, 8] | Prim 算法 | Kruskal 算法 |
|---|---|---|
| 贪心策略 | 每次选离“树”最近的点 | 每次选权值最小的边 |
| 数据结构 | 常用优先队列（最小堆）维护距离 | 常用并查集判断环，对边排序 |
| 适用图类型 | 稠密图（边数较多） | 稀疏图（边数较少） |
| 连通性要求 | 仅适用于连通图 | 可处理不连通图（生成森林） |
| 效率瓶颈 | 节点遍历与距离更新 | 对边权值的排序 |
3. 时间复杂度
假设V VV为顶点数，E EE为边数：
- Prim 算法：通常为O ( V 2 ) O(V^2)O(V2)。若使用二叉堆优化，复杂度可降至O ( E log V ) O(E \log V)O(ElogV)。
- Kruskal 算法：主要耗时在排序，复杂度为O ( E log E ) O(E \log E)O(ElogE)（或O ( E log V ) O(E \log V)O(ElogV)，因为E ≤ V 2 E \leq V^2E≤V2）。 [7]
总结建议
- 如果图非常密集（边非常多），知乎专家 建议优先选择 Prim 算法。
- 如果图比较稀疏或边已经预先排好序，使用 Kruskal 算法通常更高效。 [1, 6]
[1] https://zhuanlan.zhihu.com
[2] https://cloud.tencent.com
[3] https://developer.aliyun.com
[4] https://juejin.cn
[5] https://www.cnblogs.com
[6] https://fuxi.163.com
[7] https://oi-wiki.org
[8] https://www.liuchuo.net
