让我们假设一个 > 25000 个节点的完整图。每个节点本质上是平面上的一个点。它有 625M 的边。每条边都有长度，应该存储为浮点数。
我需要一种算法来找到它的 MST（在普通 PC 上）。
如果我采用 Kruskal 算法，它需要首先对所有边进行排序，但我什至无法同时将边完全存储在内存中。
如果我选择 Prim 的算法，很难评估同时将有多少条边存储在一个堆中，但可能在算法开始后很快就会有大部分边。
是否有任何内存足够的算法可以让我避免对存储在文件中的边进行排序？
此外，是否有任何已知的 MST 算法利用任何树边满足三角形不等式这一事实？
您仍然可以使用 Kruskal 算法。
您实际上不需要对边缘进行排序，算法所需的只是一种可重复地找到尚未使用的最小权重边缘的方法。对边缘进行预排序并遍历该列表只是一种非常有效的方法。
您可以简单地通过重复查找 k 最小的未使用边（其中 k 是一个可管理的数字，可能至少 |V|）来做同样的事情，然后根据需要对它们进行排序和迭代。这将排序过程分解为更易于管理的部分，尽管存在时间-空间权衡，因为取决于 k 的大小，此过程的时间复杂度可以从 O(E log E) (k = E) 到大约 O (E^2) (k = 1)。
Boruvka 的算法在未排序的边列表上进行对数的遍历。所需的内存与节点的数量成正比。
尝试使用此算法
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
Prim 的 MST 算法和 Dijkstra 的单源最短路径算法之间存在联系，该算法已在 Prim 的 MST 算法的 BOOST Graph Library 实现中使用：
而在 Dijkstra 算法中，当遍历最近弹出的顶点 $u$ 时，优先级队列中的顶点 $v$ 的成本函数是 $\L(s,u)+|(u,v)|$，它是相同的算法，但是使用 $|(u,v)|$ 作为产生 MST 而不是最短路径树的成本函数。
内存占用与顶点数量呈线性关系，可以采用 Dijkstra 算法的实现并相应地修改成本函数，或者使用 Prim 的 MST 算法的 BOOST Graph Library 实现。