让我们假设一个> 25000个节点的完整图表。每个节点基本上是平面上的一个点。它有625M边缘。每条边的长度应存储为浮点数。
我需要一个算法来找到它的MST（在通常的PC上）。
如果我采用Kruskal的算法，它需要先对所有边进行排序，但我甚至无法承受在内存中同时存储边缘。
如果我选择Prim的算法，那么很难同时评估堆中存储的边数，但可能大多数边将在算法启动后很快就存在。
是否有更多的内存足够的算法可以让我避免排序存储在文件中的边？
还有，是否有任何已知的MST算法利用任何树边缘满足三角不等式的事实？
你仍然可以使用Kruskal的算法。
您实际上不需要对边进行排序，算法所需的只是一种可重复查找尚未使用的最小权重边的方法。预先分配边缘并遍历该列表只是一种非常有效的方法。
你可以简单地通过重复找到k个最小的未使用边（其中k是一个可管理的数字，可能至少是| V |）来做同样的事情，然后根据需要对它们进行排序和迭代。这将分拣过程分解为更易于管理的部分，尽管存在时间 - 空间权衡取决于k的大小，该过程的时间复杂度可以是从O（E log E）（k = E）到约O的任何地方。 （E ^ 2）（k = 1）。
尝试使用此算法
1: Append weight w and outgoing vertex v per edge into a list, X.
2: Divide the edge-list, E, into segments with 1 indicating the start
of each segment, and 0 otherwise, store this in flag array F.
3: Perform segmented min scan on X with F indicating segments
to find minimum outgoing edge-index per vertex, store in NWE.
4: Find the successor of each vertex and add to successor array, S.
5: Remove cycle making edges from NWE using S, and identify
representatives vertices.
6: Mark remaining edges from NWE as part of output in MST.
7: Propagate representative vertex ids using pointer doubling.
8: Append successor array’s entries with its index to form a list, L
9: Split L, create flag over split output and scan the flag to find
new ids per vertex, store new ids in C.
10: Find supervertex ids of u and v for each edge using C.
11: Remove edge from edge-list if u, v have same supervertex id.
12: Remove duplicate edges using split over new u, v and w.
13: Compact and create the new edge-list and weight list .
14: Build the vertex list from the newly formed edge-list.
15: Call the MST Algorithm on
作者：
Vibhav Vineet
Pawan Harish
Suryakant Patidar
P. J. Narayanan
Boruvka's algorithm在未排序的边缘列表上进行对数的传递。所需的内存与节点数成正比。
Prim的MST算法与Dijkstra的单源最短路径算法之间存在联系，该算法已在Prost用于MST的算法的BOOST图库实现中使用：
而在Dijkstra算法中，当超过最近弹出的顶点$ u $时，优先级队列中顶点$ v $的成本函数是$ \ L（s，u）+ |（u，v）| $，它是相同的算法，但使用$ |（u，v）| $作为生成MST而不是最短路径树的成本函数。
内存占用量在顶点数量上是线性的，可行的方法是采用Dijkstra算法的实现并相应地修改成本函数，或者使用Prim的MST算法的BOOST Graph Library实现。