Reputation: 2887
I am newbie to Minimum spanning trees and trying to figure out which MST algorithm to use in any particular situation. Can anybody provide some examples with any particular situation where one of the MST algorithm is more suitable than others
Upvotes: 2
Views: 554
Reputation: 70931
I would say the two main solutions to the minimum spanning tree problem differ in the way the graph is represented. While Kruskal works well with edge list, Prim's algorithm will better work with a neighbourhood list. If I am left to decide on the graph representation I prefer to implement Kruskal as I find it easier to implement, but the difference is really small in that aspect- so it's up to you.
Upvotes: 1
Reputation: 2515
Check out this pdf
Quick Summery (quoting the page):
"Boruvka’s and Kruskal’s algorithms are clearly more useful if applied to the real world, while Prim’s runtime grows far too quickly with the order of the graph to be of use in a serial processing environment."
"Out of the three algorithms, Boruvka’s holds most promise when parallel computing is considered. It is parallelizable by design and involves searching locally for the smallest edge and then combining the resulting trees after each step. Division of tasks between multiple computer processing nodes would be the logical extension of Boruvka’s algorithm. However, as can be seen from this paper, Kruskal’s algorithm is much more efficient in a serial environment."
Upvotes: 2