在巨大的完整圖中找到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的算法

回答

相關問題