最小生成樹的 Prim's 演算法

Prim 的最小生成樹演算法與 Dijkstra 的單一源點最短路徑演算法相當地類似。（編按：但是演算法正確性的論述卻截然不同！） 從任意選定的源頭 \(v\) 出發，接著不斷挑選 \(v\) 所在的連通元件的最小外連邊，向外擴增這個連通元件。 演算法的步驟如下：

  1. 隨意挑選一個點 \(v\in V\)，並定義當前的連通元件點集 \(S=\{v\}\)。初始化 \(E'=\emptyset\) 為欲輸出的最小生成樹的邊所成的集合。
  2. 重複以下步驟直到 \(S=V\)：
    • 選擇任何一條從 \(S\) 連出去的邊 \(e_{min} = \arg\min_{e\in \partial S} w(e)\)。假設 \(e_{min}=(x, y)\)，其中 \(x\in S\) 並且 \(y\notin S\)。
    • 將 \(e_{min}\) 加入 \(E'\) 中，即 \(E' \gets E' \cup \{e_{min}\}\)。
    • 將 \(y\) 加入 \(S\) 中，即 \(S \gets S\cup \{y\}\)。

定理 MST.3

若輸入之圖 \(G\) 為連通，且所有邊權重皆不相等，那麼執行完 Prim's 演算法後，\(E'\) 包含圖 \(G\) 上所有的安全邊。換句話說，\(E'\) 形成了最小生成樹。

有了安全邊的定義之後，證明就會變得相當簡潔。我們假設 \(E_{\textit{safe}}\) 為圖 \(G\) 上所有的安全邊。那麼要證明的便是演算法執行完畢後，\(E'=E_{\textit{safe}}\)。

定理 MST.3 的證明

根據演算法，當 \(e_{min}\) 被加入 \(E'\) 的時候，存在一個集合 \(S\) 使得 \(e_{min}\) 是所有從 \(S\) 往外連的邊當中權重最小的一個。於是 \(e_{min}\) 是一條安全邊，因此 \(E'\subseteq E_{\textit{safe}}\)。此外，由於圖 \(G\) 是連通的，步驟 2 必定會重複恰好 \(|V\vert -1\) 次，於是有 \(|E'\vert = \vert V\vert -1\)。而因為圖 \(G\) 所有邊權重都不相等，由係理 MST.2 我們知道 \(E_{\textit{safe}}\) 的大小也是 \(|V\vert -1\)，所以得知 \(E' = E_{\textit{safe}}\)。 \(\square\)

Prim's 演算法的實作

上述的 Prim's 演算法在實作上有一個相當模糊的步驟：找出所有從集合 \(S\) 連出去權重最小的一條邊。直接枚舉所有邊，並且檢查這條邊是否跨越集合 \(S\) 的話，整個演算法的時間複雜度是 \(O(mn)\) 的。

注意到，接連兩次的步驟 2，集合 \(S\) 連出去的邊，其實並沒有相差多少。如果我們令 \(S\) 與 \(S' = S\cup \{y\}\) 分別為連續兩次步驟 2 的執行時對應到的點集合 \(S\)，那麼 \(\partial S\) 與 \(\partial S'\)，僅差在與 \(y\) 相連的那些邊。

於是，我們可以使用一個支援插入、刪除與取得最小值的堆積資料結構（heap），來實作這個步驟。由於每一個步驟所需要的插入與刪除數量是 \(O(\text{deg}(y))\)，因此整體的時間複雜度變下降為 \(O(m\log m)\)。

利用 Dijkstra 單一源點最短路徑的想法進行實作

現在我們想像一下，如果資料結構中，同時間出現兩條以上連至某個點 \(y\) 的邊，顯然權重比較大者最終絕對不會被選用。也就是說，對於每個不在 \(S\) 的點 \(y\) 中，只需要維護一條「從 \(S\) 中某個點連至 \(y\) 最小權重的邊」即可。基於這個想法，每次發現有一條新的邊連至 \(y\) 的時候，我們只需要與原本維護的這條邊比較看看，決定是否更新連至 \(y\) 的權重即可。於是，我們可以使用一個支援插入、降低鍵值、刪除最小值與取得最小值的資料結構，來時做這個步驟。

與 Dijkstra 演算法相同的部分是，我們需要的插入與刪除最小值的次數為 \(O(n)\)（恰好執行 \(n-1\) 次）、降低鍵值的次數為 \(O(m)\)。因此採用 Fibonacci Heap 或是 Brodal Queue，可以讓整個 Prim's 演算法複雜度降至 \(O(m + n\log n)\)。

參考資料