krukshal算法和Prims算法哪个在寻找最小生成树方面更好？
可能的重复：
克鲁斯卡尔与普里姆
krukshal 算法或 Prims 算法哪个在寻找最小生成树方面更好？
Possible Duplicate:
Kruskal vs Prim
krukshal's algorithm or Prims Algorithm which one is better in finding minimum spanning tree?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我将添加一点赞成 Prim 的算法，但我没有看到提及。如果给定 N 个点和 x 与 y 之间距离的距离函数 d(x,y)，则使用空间 O(N)（但时间 N^2）很容易实现 Prim 算法。
从任意点 A 开始，创建一个大小为 N-1 的数组，给出从 A 到所有其他点的距离。选择与最短距离关联的点 B，在生成树中链接 A 和 B，然后将数组中的距离更新为已记下的到该其他点的距离以及到该其他点的距离中的最小值点，记下从 B 到 A 的最短链接。继续。
我不知道处理由距离函数指定的密集图的 Kruskal 算法的类似方法，并且对于大 N，在您失去耐心的时间 O(N^ 之前，您可能会用完空间 O(N^2) 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).