在巨大的完整图中找到MST的算法 [英] Algorithm to find MST in a huge complete graph

问题描述

让我们假设一个完整的图表包含25000个以上的节点。每个节点本质上都是平面上的一个点。
它有6.25亿条边。每个边的长度应存储为浮点数。

Let's assume a complete graph of > 25000 nodes. Each node is essentially a point on a plane. It has 625M edges. Each edge has length which should be stored as a floating point number.

我需要一种算法来查找其MST（在普通PC上）。

I need an algorithm to find its MST (on a usual PC).

如果我采用Kruskal算法，则需要首先对所有边进行排序，但我什至无法承受将所有边同时存储在内存中。

If I take Kruskal's algorithm, it needs to sort all edges first, but I cannot afford even store the edges altogether in memory at the same time.

如果我选择Prim的算法，很难同时评估在堆中存储多少个边，但是其中大多数可能会非常算法开始后不久。

If I choose Prim's algorithm, it's quite difficult to evaluate how many edges will be stored in a heap at the same time, but probably the most of them will be there very soon after algorithm starts.

是否还有其他内存足够的算法可以使我避免对存储在文件中的边缘进行排序？

Is there any more memory-sufficient algorithm which can allow me to avoid sorting edges stored in a file?

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

Also, are there any known MST algorithms which utilize the fact that any tree edges satisfy triangle inequality?

推荐答案

您仍然可以使用Kruskal算法。

You can still use Kruskal's algorithm.

您不这样做如果实际上需要对边缘进行排序，则算法所需的只是简单的方法，该方法可重复地找到尚未使用的最小权重边缘。对边缘进行预排序并遍历该列表只是这样做的一种非常有效的方法。

You don't actually need to sort the edges, what the algorithm requires is simply a method for repeatably finding the smallest weight edge that hasn't already been used. Presorting the edges and iterating through that list is simply a very efficient way of doing so.

您可以通过重复查找k个最小的未使用边（其中k是一个可管理的数字，可能至少是| V |）来完成相同的操作，然后进行排序和而是根据需要遍历它们。尽管存在时空折衷，这取决于排序的时间复杂度，但该过程的时间复杂度可以从O（E log E）（k = E）到O左右，这将排序过程分为更易于管理的段。 （E ^ 2）（k = 1）。

You can do the same thing simply by repeatably find the k-smallest unused edges (where k is a manageable number, probably at least |V|), then sort and iterate through them instead as needed. This breaks the sorting process down into more manageable segments, although there is a time-space tradeoff as depending on how large k is the time complexity of this process can be anywhere from O(E log E) (k = E) to about O(E^2) (k = 1).

这篇关于在巨大的完整图中找到MST的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！