algorithm - krukshal 算法或 Prims 算法哪一个更适合找到最小生成树？

Question

可能的重复：
Kruskal vs Prim

krukshal 算法或 Prims 算法哪一个更适合找到最小生成树？

Answer 1

我将添加一点来支持我没有提到的 Prim 算法。如果给定 N 个点和 x 和 y 之间距离的距离函数 d(x,y)，则使用空间 O(N)（但时间 N^2）很容易实现 Prim 算法。

从任意点 A 开始并创建一个大小为 N-1 的数组，为您提供从 A 到所有其他点的距离。选择与最短距离相关联的点 B，在生成树中链接 A 和 B，然后将数组中的距离更新为已记录到该另一点的距离和从 B 到另一点的距离的最小值点，记下最短链接从 B 到哪里，从 A 到哪里。继续。

对于由距离函数指定的密集图，我不知道类似的处理 Kruskal 算法的方法，对于大 N，您可能会用完空间 O(N^2)，然后再用完 O(N^) 时间2）。