最快最小生成樹算法

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

我期待我的基準最小生成樹對最好的最好的樹算法。 有人知道我在哪裏可以找到這些算法的C++實現嗎？我瘋狂搜索並沒有發現任何東西。如果這些算法是最好的，肯定肯定有一個C++實現的地方？

最快最小生成樹 算法迄今被 大衛·卡爾格，菲利普·克萊恩和羅伯特 的Tarjan，誰發現基於Borůvka的算法和 反向的 組合 隨機算法的線性時間內開發 - 刪除算法[2] [3] Bernard Chazelle最快的非隨機算法， ，基於 軟堆，優先級爲 隊列。[4] [5]它的運行時間是O（m α（m，n）），其中m是邊的數量，n是頂點的數量，並且α是阿克曼函數的經典函數逆 。函數α增長非常緩慢，因此對於所有實際目的而言，它可能被認爲是不大於4的常數，不大於 。因此Chazelle的算法 需要非常接近線性時間。如果 邊緣權重是具有有限位長度的整數，那麼確定性算法以線性 運行時間已知。[6]如果 運行時間爲0，是否存在 確定性算法與線性 一般權重的運行時間是 仍然是一個未解決的問題。然而，Seth Petie和Vijaya Ramachandran有 找到了一個可證明的最優生成樹算法，其中 的計算複雜度爲 未知[7]。

我已經測試了Boost C++的圖算法。

Answer 1

當維基百科頁面顯示「最快的最小生成樹算法」時，它們意味着具有最低漸近界的算法 - 在這種情況下，O（mα（m，n））與m，n ，並按照您粘貼的報價定義α。簡而言之，這意味着對於非常大的輸入值，對於C的某個值，所花費的時間量將總是以C * m *α（m，n）爲界。但請注意，C可能非常大 - 即，當應用於較小的輸入值時，這種算法可能比其他算法慢，即使它對於非常大的輸入值而言比其他算法快。

當比較兩種算法的漸近邊界時，沒有「測試」來查看哪個更快 - 只需證明每個算法的漸近邊界，並查看哪個更低。 （「漸近」，是指行爲作爲輸入大小趨於無窮大 - 而且很難運行具有無限大小的輸入值測試。）

但是請注意，有這樣的情況，你應該不使用漸近最快的算法。如果「C」非常大，那麼對於較小的數據值，使用更簡單的算法可能會更好。

我的猜測是，你的算法可能會改善C，但不是漸近的邊界。但如果我錯了，那麼你應該把它提交給ACM！

欲瞭解更多信息，請參見：http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf 「分揀，亂堆，最小生成樹」， 貢薩洛納瓦羅和羅德里戈·帕雷德斯

提供了一些「最好的」內核和外部存儲器測量結果，並提供了對舊版本 實現的參考。

他們報告的I/O＃和CPU時間 圖形大小的功能，並說明他們的測試用例好，所以 原則上你可以做的測試，以及與 其公佈的圖表進行比較。您可以使用他們的Prim2 參考（來自Peter Sanders的代碼，他可以免費提供其許多快速代碼的 ）來校準您自己的測量結果 。