Kruskal vs Prim
183 algorithm graph-theory minimum-spanning-tree prims-algorithm kruskals-algorithm
我想知道什么时候应该使用Prim的算法,什么时候Kruskal才能找到最小的生成树？它们都具有简单的逻辑,同样最坏的情况,唯一的区别是实现可能涉及一些不同的数据结构.那么决定因素是什么？
Tod*_*lin 192
当您有一个包含大量边的图时,请使用Prim的算法.
对于具有V顶点E边的图,Kruskal的算法在O(E log V)时间内运行,而Prim的算法可以在O(E + V log V)的摊销时间内运行,如果使用斐波那契堆.
当你有一个比顶点更多的边缘的真密图时,Prim的算法明显更快.Kruskal在典型情况下(稀疏图)表现更好,因为它使用更简单的数据结构.
- 这在理论上听起来不错,但我敢打赌,很少有人可以实现Fibonacci堆 (9认同)
- 我会说"典型情况"而不是平均值.我认为这是一个不起眼的术语,例如哈希表的"平均大小"是什么？不知道. (7认同)
- 还有另一个重要因素:Prims的输出仅在连接图形时才是MST(输出在我看来没有用),但Kruskal的输出是最小生成范围森林(有一些用途). (6认同)
- @SplittingField：我相信你是在比较苹果和橙子。摊销分析是一种获得函数测量的简单方法（可以这么说）——无论是最坏的情况还是平均情况都取决于您要证明的内容。事实上（正如我现在查找的那样），维基文章使用的语言暗示其*仅*用于最坏情况分析。现在，使用这样的分析意味着你不能对特定操作的成本做出如此强烈的承诺，但是当算法完成时，它确实会达到 O(E+VlogV)，即使是最坏的情况。 (3认同)
- 谁需要实施一项？只需谷歌搜索现有的实现即可。斐波那契堆自 1987 年以来一直存在。 (2认同)
- @tgamblin,在最坏的情况下可能有C(V,2)边.那么,在斐波那契堆的情况下,Prim算法的时间完全不会归结为O(V ^ 2 + VlogV),即O(V ^ 2)？ (2认同)
Sni*_*las 97
我在网上发现了一个非常好的线程,以一种非常简单的方式解释了它的不同之处:http://www.thestudentroom.co.uk/showthread.php？t = 232168.
Kruskal的算法将通过添加下一个最便宜的边缘从最便宜的边缘增长解决方案,前提是它不会创建一个循环.
Prim的算法将通过添加下一个最便宜的顶点来增加随机顶点的解决方案,该顶点当前不在解决方案中但通过最便宜的边缘连接到顶点.
附件是关于该主题的有趣表格.
如果你以最佳形式同时实现Kruskal和Prim:分别使用union find和finbonacci堆,那么你会注意到与Prim相比,Kruskal如何易于实现.
使用斐波纳契堆的Prim更难,主要是因为您必须维护一个记账表来记录图节点和堆节点之间的双向链接.使用Union Find,相反,结构简单,甚至可以直接生产mst,几乎不需要额外费用.
- Nitpick:每个中的最后一个"幻灯片"应该是"重复,直到你有一棵生成树"; 直到MST,这是一个递归任务 - 我怎么知道它是最小的 - 这就是为什么我开始跟随Prim/Kruskal的原因! (2认同)
mal*_*ouk 28
我知道你没有要求这个,但如果你有更多的处理单元,你应该总是考虑Borůvka的算法,因为它可能很容易并行化 - 因此它比Kruskal和Jarník-Prim算法具有性能优势.
小智 16
Kruskal时间复杂度最差的情况是O(E log E),这是因为我们需要对边缘进行排序. 最坏情况下的Prim时间复杂度是具有优先级队列的O(E log V)或者甚至更好,具有Fibonacci Heap的O(E + V log V).当图形稀疏时,我们应该使用Kruskal,当边缘已经排序或者我们可以在线性时间内对它们进行排序时,可以使用边缘的小数量,例如E = O(V).当图形密集时,我们应该使用Prim,即边数很高,如E = O(V²).
Kruskal算法的一个重要应用是单链路聚类.
考虑n个顶点,你有一个完整的图.要获得那些n个点的ak簇.运行Kruskal的算法在有序边集的第一个n-(k-1)边上.你得到图的k-簇最大间距.