2

Possible Duplicate:
Kruskal vs Prim

When would you use Kruskal's algorithm over Prim's algorithm to find the minimum spanning tree? What kind of input graphs and nodes are beter for each kind? In what cases is it more efficient to use one of them when it comes to space and time?

Are their particular inputs that make one much better than the other?

Community
  • 1
  • 1
Georges Krinker
  • 2,259
  • 4
  • 25
  • 24

1 Answers1

6

One important difference: if your graph is disconnected, Prim's will do you no good (requires the graph to be connected). Kruskal's on the other hand will work on a connected graph or a disconnected graph; in the latter case it finds the minimum spanning forest, the MST of each connected component.

kaveman
  • 4,339
  • 25
  • 44