秩VS普里姆 [英] Kruskal vs Prim

问题描述

我在想，当一个人应该使用 Prim算法时的Kruskal's 找到最小生成树？他们都可以很方便的逻辑，同样的最坏的情况，而唯一的区别就是实施可能涉及一个有点不同的数据结构。那么，什么是决定因素？

I was wondering when one should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor?

推荐答案

使用Prim算法当你有很多边缘的曲线图。

Use Prim's algorithm when you have a graph with lots of edges.

有关用图表的 V 顶点电子邮件的边缘，Kruskal算法在运行的 0（E日志V）时间和Prim算法可以运行 O（E + V登录V）摊销的时间，如果你使用斐波那契堆

For a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.

Prim算法是显著的极限速度更快，当你有一个非常密集的图，很多比顶点更多的边。秩执行在典型情况（稀疏图）更好，因为它使用简单的数据结构。

Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.

这篇关于秩VS普里姆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！