最小生成樹的 Borůvka-Prim 演算法

如果借助費氏堆積 (Fibonacci Heap) 或 Brodal Queue 等可合併堆積資料結構，那麼 Prim's 演算法可以在 \(O(m + n\log n)\) 的時間內找出最小生成樹。

若預先進行 \(\log\log n\) 次 Borůvka 步驟後，根據引理 MST.7，縮完連通元件的圖，其點數至多只有 \(n' \le n/\log n\) 個點。若我們直接在此時套用上述 Prim's 演算法，那麼便能夠在 \(O(m+n'\log n')= O(m+n)\) 線性時間計算出最小生成樹！