在巨大的完整图中找到 MST 的算法

Question

让我们假设一个包含 > 25000 个节点的完整图。每个节点本质上是平面上的一个点。它有 625M 条边。每条边都有长度，应存储为 float 。

我需要一个算法来找到它的 MST(在普通 PC 上)。

如果我采用 Kruskal 算法，它需要先对所有边进行排序，但我什至不能同时将边全部存储在内存中。

如果我选择 Prim 的算法，很难评估同时将多少条边存储在堆中，但可能大多数边会在算法开始后很快就存在。

是否有更多内存充足的算法可以让我避免对存储在文件中的边进行排序？

此外，是否有任何已知的 MST 算法利用任何树边都满足三角不等式这一事实？

Answer 1

您仍然可以使用 Kruskal 算法。

您实际上不需要对边进行排序，算法所需要的只是一种重复查找尚未使用的最小权重边的方法。对边进行预排序并遍历该列表是一种非常有效的方法。

您可以简单地通过重复找到 k 条最小的未使用边(其中 k 是一个可管理的数字，可能至少为 |V|)来完成相同的操作，然后根据需要对它们进行排序和迭代。这将排序过程分解为更易于管理的部分，尽管存在时空权衡，因为取决于 k 的大小，此过程的时间复杂度可以从 O(E log E) (k = E) 到大约 O (E^2) (k = 1).