Prim就是加点法，而Kruskal是加边法

Prim 算法和 Kruskal 算法都是求解图的最小生成树（MST）的经典贪心算法，但它们在核心策略和适用场景上有显著区别：

1. 核心思想与操作对象

• Prim 算法（加点法）：
• 思想：从图中任意一个节点开始，每次选择与当前已构建生成树距离最近（权值最小）的一个节点及其相连的边，加入到生成树中。
  • 操作对象：以顶点为中心，像“生长”一样从一点扩散到整个图。
• Kruskal 算法（加边法）：
• 思想：将图中所有的边按权值从小到大排序，每次选择权值最小且不会与已选边形成环的边，加入到生成树中。
  • 操作对象：以边为中心，在任意时刻可能产生多个不连通的分支（森林），最终合并为一棵树。 [1, 2, 3, 4, 5, 6]

2. 关键区别对比

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