prime和kruscal算法的区别

Question

如题所述

Answer 1

Prime算法和Kruscal算法的区别如下：

Prime算法在稠密图中比Kruskal算法好，在稀疏图中Prime算法比Kruskal算法差。

Prime算法+Heap算法在任何时候都有令人满意的的时间复杂度，但是代价是空间消耗极大。

时间复杂度并不能反映出一个算法的实际优劣。

如图所示：

总结：若是所给的题大多数是稀疏图，所以尽可能地使用Prime算法+Heap算法吧，在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prime的代码比较简单，比较简单的题用Prim也无所谓，只要不是极稀疏图的题两者相差都不大。

Answer 2

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。
kruskal算法，求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪心准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。
所以二者的区别是，边数较少可以用Kruskal,因为Kruskal算法每次查找最短的边。 边数较多可以用Prim，因为它是每次加一个顶点，对边数多的适用。

官方电话