4

Possible Duplicate:
Kruskal vs Prim

krukshal's algorithm or Prims Algorithm which one is better in finding minimum spanning tree?

Community
  • 1
  • 1
Eric
  • 111
  • 7
  • 1
    @Adnan: how do you know this is homework? – R. Martinho Fernandes Nov 22 '10 at 03:51
  • http://stackoverflow.com/questions/1195872/kruskal-vs-prim – Eric Nov 22 '10 at 03:51
  • Sounds very familiar to my algorithms analysis class question from a few years back – Adnan Nov 22 '10 at 03:52
  • Simple answer: they're both still in wide/common use because either can be better depending on the nature of your graph, specifically number of nodes versus number of edges. – Jerry Coffin Nov 22 '10 at 03:55
  • I took off the tag since it offended you so much and apparently it isn't homework. It wasn't meant to be offensive or accusatory, just trying to make this Q visible under homework tag. – Adnan Nov 22 '10 at 04:02

1 Answers1

2

I'll add one point in favour of Prim's algorithm I haven't seen mentioned. If you are given N points and a distance function d(x,y) for the distance between x and y, it is easy to implement Prim's algorithm using space O(N) (but time N^2).

Start off with an arbitrary point A and create an array of size N-1 giving you the distances from A to all other points. Pick the point, B, associated with the shortest distance, link A and B in the spanning tree and then update the distances in the array to be the minimum of the distance already noted down to that other point and the distance from B ot that other point, noting down where the shortest link is from B and where from A. Carry on.

I don't know a similar way of handling Kruskal's algorithm for a dense graph specified by a distance function, and for large N you can run out of space O(N^2) before you run out of patience for time O(N^2).

mcdowella
  • 19,301
  • 2
  • 19
  • 25