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

让我们假设一个> 25000个节点的完整图。每个节点本质上是一个平面上的一个点。它有625M的边缘。每条边的长度都应该作为浮点数存储。在巨大的完整图中找到MST的算法

我需要一种算法来找到它的MST（在通常的PC上）。

如果我参加Kruskal算法，它需要所有的边第一排序，但我买不起甚至完全在内存中同时存储的边缘。

如果让我选择Prim算法，这是相当难以评估有多少边缘将在同一时间被存储在一个堆，但可能他们中的大多数将很快算法开始后在那里。

是否有更多的内存，足够的算法，它可以让我避免排序存储在文件中的边缘？

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

来源

2013-07-03 Roman

图表是否完整？ 625M只有25000 ** 2。此外，这里http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree –

也有库这样的：http://www.mlpack.org/doxygen.php?doc=emst_tutorial.html –

@ZiyaoWei：谢谢，这看起来像我正在寻找的东西。 – Roman

尝试使用这种算法

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

Source

来源

2013-07-03 14:33:05

听起来非常复杂。 – Fabinout

也是问题，不是吗？ @Fabinout –

另外，MST代表法国的STD，所以...比人们想象的更难。 @Jayram – Fabinout

，您仍然可以使用Kruskal算法。

你实际上并不需要的边缘，有什么算法要求简直是重复地发现尚未使用的最小重量边缘的方法排序。预设边界并遍历该列表只是一个非常有效的方法。

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

来源

2013-07-03 17:29:48 Nuclearman

Boruvka's algorithm在未排序的边界列表上进行对数次通过。所需的内存与节点数量成正比。

来源

2013-07-03 18:25:57

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

回答

相关问题