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?
+9
A:
Use Prim's algorithm when you have a graph with lots of edges.
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'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.
tgamblin
2009-07-28 18:36:55
I would say "typical situations" instead of average.. I think it's an obscure term to use, for example what is the "average size" of a hash table? no idea.
yairchu
2009-07-29 11:28:02
Don't forget to add that Prim's + Fibonacci heaps gives an amortized running time, not a worst case running time.
SplittingField
2009-07-30 16:25:51
@SplittingField: I do believe you're comparing apples and oranges. Amortized analysis is simpy a way of getting a measurement of the function (so to speak) --- whether it is the worst case or average case is dependent on what you're proving. In fact (as I look it up now), the wiki article uses language that implies that its *only* used for worst-case analysis.Now, using such an analysis means that you can't make as strong promises about the cost of a particular operation, but by the time the algorithm is done, it will indeed by O(E+VlogV), even worst-case.
Agor
2009-07-30 16:49:11
That sounds good in theory, but I bet few people can implement a Fibonacci heap
Alexandru
2009-10-29 20:04:18
Who needs to implement one? Just google for an existing implementation. Fibonacci heaps have been around since 1987.
tgamblin
2009-10-29 22:32:00
+2
A:
Kruskal can have better performance if the edges can be sorted in linear time, or are already sorted.
Prim's better if the number of edges to vertices is high.
Daniel
2009-07-28 18:43:52