最小生成樹的 Borůvka's 演算法

捷克數學家 Otakar Borůvka 早在 1926 年就已經提出解決最小生成樹問題的演算法了，但由於以捷克文寫成的，當時又在一次世界大戰，所以他的論文並沒有快速地流通全世界。 相同概念的演算法稍後在 1938 (Choquet, 法國), 1951 (Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki, 法國), 1965 (Sollin, 法國) 年也被多次重新發現並且發表。

Borůvka's 演算法

Borůvka 觀察到一件非常重要的事情：假設圖 \(G\) 是一個連通且邊權重皆相異的圖。對於每一個點連出去的所有邊中，權重最小的邊必定屬於最小生成樹。這個觀察非常重要，顯然它是安全邊定義中的一個特例（集合 \(S\) 內恰好只包含一個點）。現在對所有點分別選擇一條連出去權重最小的邊，這些邊是最小生成樹中的子集合。也就是說，如果此時我們把藉由這些邊直接或間接的點，全部縮起來，那麼縮起來的圖上面的最小生成樹，一定就是原本圖 \(G\) 上面的最小生成樹，將對應位置的點集合縮起來之後的結果。我們可以把上面這個觀察寫成以下的引理：

引理 MST.5

假設圖 \(G\) 是一個連通且邊權重皆相異的圖。令 \(T=\text{MST}(G)\) 是圖 \(G\) 上的最小生成樹。 令 \(S\subseteq T\) 是 \(T\) 上的一棵子樹，那麼將 \(S\) 上的所有點收縮起來得到的圖 \(H := G\circ S\)，其最小生成樹 \(\text{MST}(H) = T\circ S\)。

引理 MST.5 的證明

首先，我們知道因為 \(S\) 是一棵子樹，所以縮起來以後 \(T\circ S\) 是一棵樹（連通的、恰好有 \(n-\vert V(S)\vert +1\) 個點、恰好有 \(n-1-\vert E(S)\vert \) 條邊）。不妨以 \(v_S\) 代表將 \(S\) 所有節點縮起來以後的點。 其次，\(H\) 上的每一條邊權重顯然都不同，且 \(H\) 連通。因此我們只要證明 \(H\) 裡的安全邊恰好是 \(T\circ S\) 的所有邊就行了。 考慮任何 \(H\) 上的一條安全邊 \(e_H\)，其對應在圖 \(G\) 上的邊為 \(e_G\)。

\(e_H\) 這條安全邊對應到的集合 \(X\subseteq V(H)\) 如果包含了 \(v_S\)，那麼 \(e_G\) 也會是 \(X\setminus\{v_S\}\cup S \subseteq V(G)\) 往外連的邊中權重最小的。如果 \(v_S\notin X\)，那麼 \(e_G\) 也會是 \(X\subseteq V(G)\) 外連邊中權重最小的。因此我們有 \(\text{MST}(H)\subseteq T\circ S\)。由於邊數相同，因此 \(\text{MST}(H)=T\circ S\)，得證。

如果我們反覆重複「找外連的最小邊」、「把連在一起的子樹縮起來」這兩件事情，當所有點都連起來的時候，我們就得到最小生成樹啦！

Borůvka 演算法步驟如下：

  1. 初始化 \(E'=\emptyset\) 為欲輸出的最小生成樹的邊所形成的集合。
  2. 重複以下動作直到 \(G\) 剩下一個點：
    • 對每一個 \(V(G)\) 中的點選擇連出去權重最小的邊，將這些邊的原始參照加入 \(E'\) 中。
    • 這些邊會形成森林 \(F\)，找出這個森林的連通元件 \(S_1, S_2, \ldots, S_k\)，並且對每一個點 \(v\) 找出其對應的連通元件編號 \(\sigma(v)\)。
    • （建立縮點後的圖）建立新的圖 \(G^*=(V^*, E^*)\)，其中 \(V^*=\{1, 2, \ldots, k\}\)，對於 \((u, v)\in E\)，如果 \(\sigma(u)\neq \sigma(v)\)，我們就把一條相同權重的 \((\sigma(u), \sigma(v))\) 邊加入 \(E^*\) 裡面，並且保留圖 \(G\) 中的原始參照。
    • 把 \(G\) 換成 \(G^*\)。

Borůvka 演算法的實作

實作的部分相對於 Prim's 或 Kruskal's 演算法來說就直接了些。找出連通元件的部分可以利用 BFS 或 DFS 在 \(O(m+n)\) 的線性時間做到，而製作新的圖所需的時間也是線性的。

Borůvka 演算法的分析

正確性的證明：引理 MST.6

輸出之 \(E'\) 包含所有 \(G\) 上最小生成樹的邊。

引理 MST.6 的證明

假設步驟 2 每一次執行時對應的圖為 \(G_0=G, G_1, G_2, \ldots, G_t\)。每次執行時演算法都會將 \(G_i\) 內的某些安全邊加入 \(E'\) 中，而根據引理 MST.5，這些邊都是 \(G_{i-1}, G_{i-2}, \ldots, G_0\) 上的安全邊，因此 \(E'\) 內的所有邊都是輸入的圖 \(G\) 中的安全邊。 此外，我們可以透過觀察得知，針對 \(G_i\) 執行步驟 2 之後，對於新的圖 \(|E'\vert + V(G_{i+1})\) 恆等於 \(n\)。因此當演算法停止時，我們得到 \(|E'\vert =n-1\)，因此 \(E'\) 包含了所有圖 \(G\) 上的安全邊，根據定理 MST.1，\(E'\) 包含了最小生成樹上的所有邊。 \(\square\)

時間複雜度：引理 MST.7

對於任何 \(i\)，\(|V(G_{i+1})\vert \le \vert V(G_{i})\vert / 2\)。

引理 MST.7 的證明

考慮步驟 2 形成的森林 \(F\)。在這個森林的 \(k\) 個連通元件中，每一個連通元件至少包含兩個點，因此必定有 \(|V(G_i)\vert \ge 2k\)，即 \(|V(G_{i+1})\vert =k \le \vert V(G_i)\vert /2\)。 \(\square\)

由引理 MST.7 不難發現步驟 2 至多只會執行 \(O(\log n)\) 次，因此 Borůvka 演算法執行總時間為 \(O(m\log n)\)。

參考資料