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

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

Kruskal vs Prim

krukshal's algorithm or Prims A开发者_如何学JAVAlgorithm which one is better in finding minimum spanning tree?

---

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).