利用線程實現克魯斯卡爾算法

Question

我正在實現克魯斯卡爾算法，我想利用線程。但是我不確定我是否足夠了解該算法。

我想象的是，我會在圖表的不同部分解決並連接到最後。任何人都可以將我指向正確的方向嗎？謝謝。

Answer 1

從Wikipedia

研究主要集中於在 高度並行的方式解決 最小生成樹問題。用 線性處理器數量是 可能解決 O（logn）時間的問題。 2003年的論文「快速 共享內存算法計算 稀疏 圖的最小生成森林」由David A.貝德和國經 叢演示務實 算法，可以計算MSTS快5倍 上8個處理器比 優化的順序算法。[9]通常，並行算法是基於Boruvka算法-Prim的 並且特別是Kruskal的算法做的 並不擴展到另外的 處理器的並行算法 。

因此，您可以看看該論文中提到的算法，但克魯斯卡爾可能不會從多個線程中受益。

Answer 2

Kruskal的MST算法很難並行化，因爲它考慮嚴格指定順序的邊緣。您應該看看Boruvka's算法，該算法更容易並行化，因爲它可以獨立處理部分MST的每個子樹。