1. 設定與問題
設 為一個有限、連通、無向、無自環的簡單圖,其中 。設 為權函數。權可以是負數,多條邊亦可以有相同的權。固定一個整數 ,使得 。
定義
(生成森林及其權)
生成森林是一個無環的邊集 ,並視為定義在全部 個頂點之上。其權為 。
問題。 在所有恰好有 個連通分支的生成森林之中,找出一個權最小者。
2. 以邊數刻畫
引理
(森林的連通分支)
一個在 個頂點上的森林 恰好有 個連通分支。
證明
(逐條邊計算連通分支數)
從沒有邊的狀態開始,此時共有 個連通分支。將 的邊逐條加入。每條加入的邊都屬於無環集 ,因此在加入的一刻,它的兩個端點位於不同的連通分支,否則它會閉合成一個環。所以每次加入都令連通分支數目恰好減少一。
因此,一個森林恰好有 個連通分支,當且僅當它恰好有 條邊。可行的森林必定存在。由於 是連通的,它有一棵含 條邊的生成樹;刪去其中任意 條邊,便得到一個含 條邊的森林。若一個森林在所有含 條邊的森林之中權最小,便稱之為最優森林。
3. 算法與同權處理規則
同權處理規則。 將邊任意但固定地編號為 。然後按序對 以字典序排列各邊。這是一個嚴格全序 。下文凡說「 排在 之後」,均指按 而言,並且由此可推出 。
算法 。
- 初始化一個併查集結構,每個頂點各自成一個單元素集合。設 。
- 按 的次序掃描各邊。對每條邊 ,若 ,則立即停止。否則,若 ,則將 加入 並執行 。若兩次 find 的結果相同,則拒絕 。
- 輸出 。
若 ,算法不接受任何邊,直接輸出 。
終止時邊數足夠。 假設掃描結束時 。那麼 有多於 個連通分支。由連通性,存在某條邊 連接兩個不同的最終連通分支。連通分支只會隨時間合併,所以在掃描 時, 與 位於不同的連通分支。這樣算法便會接受 ,產生矛盾。因此 ;又因為每條被接受的邊都連接兩個不同的連通分支,所以 是一個森林。
4. 正確性:交換不變量
定理
(提前停止 Kruskal 算法的正確性)
設 為有限、連通、無向的簡單圖, 為任意實數權函數(容許負權和同權),,並按 排列各邊。則 輸出一個恰有 個連通分支的生成森林,其權在所有這類森林中最小;也就是說,它輸出一個最優森林。
證明
(建立交換不變量)
設 為按接受次序排列的被接受邊,並設 。
不變量 。 存在某個最優森林包含 。
顯然成立。當 時,有一個最優森林包含 ,而兩者都有 條邊,所以該最優森林等於輸出。餘下只需證明:對於 , 蘊含 。
假設 是最優的,且 。設 。若 ,則已完成。否則,可應用以下關鍵引理。
引理
(最優森林中的邊排在較後)
設 為最先被接受的 條邊, 為滿足 的森林, 為下一條被接受的邊,且 。則每個 按 都排在 之後。
證明
(較早被拒絕的邊會形成環)
假設 。在掃描 之前被接受的邊恰好是 。由於 , 曾被拒絕。在那一刻,它的兩個端點由某個 中的一條路徑連接。該路徑連同 在 內構成一個環,與無環性矛盾。另外,由於 ,所以 。
證明
(分兩種情況的交換步驟)
現在考慮 。以下兩種情況恰有一種出現。
情況 A: 連接 的兩個不同連通分支。 那麼 仍是一個森林,因為它不會產生環,而它有 條邊。我們需要移除一條邊。計數:,所以可任選 。從森林中移除一條邊後仍是森林。所以 是一個含 條邊的森林,且 。由後繼邊引理,,因此 。故 是最優的。
留意這種情況在一般生成樹的證明中不可能出現,因為在那裏 是連通的。在這裏 可能有 個連通分支,所以必須處理這種情況。
情況 B: 的兩個端點都位於 的同一個連通分支。 那麼 包含唯一一個經過 的環 。集合 是一個森林,所以 。選取 。那麼 ,所以 。刪去環上的一條邊會保持該連通分支內的連通性。因此 是一個與 有相同連通分支的森林,它有 條邊,並且包含 。由後繼邊引理,。
在兩種情況下 均成立。
證明中沒有任何地方用到 的正負號。負權及同權的情況均已完全涵蓋。
證明透視
為何交換論證適用於森林
保持一個包含目前已選邊的最優森林。若下一條接受邊在該森林中形成環,就刪去環上的另一條邊;若它連接最優森林的兩個分支,加入後不會形成環,可以刪去已選前綴以外的任意一條邊。兩種情況下,被刪去的邊都比新接受邊較遲被考慮:若它較早且被拒絕,就會在最優森林中形成環。因此被刪去邊的權重不小於新邊,交換仍得到最優森林。
5. 示範追蹤
例題
(含負權與同權的提前停止 Kruskal)
取 ,頂點為 ,並取 。目標是 條邊。
| 編號 | 邊 | 權 |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 |
的次序為 。 與 同權,按編號 決定先後; 與 同權,按編號 決定先後。
| 步驟 | 邊 | find 結果相同? | 動作 | 連通分支 | |
|---|---|---|---|---|---|
| 1 | 否 | 接受 | 1 | ||
| 2 | 否 | 接受 | 2 | ||
| 3 | 否 | 接受 | 3 | ||
| 4 | 是 | 拒絕 | 3 | 不變 | |
| 5 | 否 | 接受 | 4 |
掃描在 時停止。輸出為 ,其權為 。
例題
(相反的同權處理規則給出另一個最優森林)
同權處理會影響輸出哪一個森林,但不影響其權。 若對權為 3 的邊採用相反的同權處理規則,算法便會接受 而非 。這樣得到 ,其連通分支為 和 ,權同樣是 。兩個森林都是最優的,而固定的規則只是令輸出具確定性。
例題
( 的兩個極端值)
沿用追蹤中的圖。當 時,目標為 條邊,所以掃描在接受任何邊之前就停止,輸出權為 的 :六個單點分支。當 時,目標為 條邊,掃描會越過追蹤中的停止點。、、 被接受, 被拒絕, 如前被接受。由於 ,掃描繼續:(權 ,編號 )把 接到大分支上,於是 ,掃描停止。輸出 是權為 的最小生成樹。最後被接受的邊權為正;恰有一個連通分支時,算法必須接受它。
常見錯誤
(在 k 條邊而不是 n-k 條邊時停止)
掃描在接受 條邊時停止,而不是 條。在 、 的追蹤中,若接受兩條邊就停止,會輸出 ,它有四個連通分支。只有 時兩個數目才相同。
常見錯誤
(因為權為正而拒絕一條邊)
由於問題要求恰有 個連通分支,算法必須不斷接受邊直到有 條,即使下一條可接受的邊權為正。在追蹤中, 的權為 但被接受;若把它捨棄,就只剩三條邊、三個連通分支的森林,那是另一個問題。
6. 恰好、至多及至少 個連通分支
每個 都進行相同的掃描,只是停止的時刻不同。因此 是在 的基礎上再加入下一條被接受的邊。記 為恰好有 個連通分支時的最優權。此例中完整的掃描依次接受 ,由此得到:
| 6 | 5 | 4 | 3 | 2 | 1 | |
|---|---|---|---|---|---|---|
概念視角結構
最優森林就是去掉最重邊的生成樹
由於 是 的延伸,具 個連通分支的最優森林,就是把最小生成樹中最後接受的 條邊刪去所得的森林。在這裏,樹 刪去 便得出兩個連通分支的最優森林,權重為 ;再刪去 ,便得出三個連通分支的最優森林 ,權重為 。因此停止規則只是對同一棵樹的一次截斷,而序列 記錄的是這棵樹各個前段的權重。
這個序列先下降後上升。在有負權的情況下, 與最優值之間沒有單調關係。每多加一條邊便加上它本身的權,而該權可正可負。
- 至多 個連通分支即至少 條邊。最優值為 。當 時,此值為 。
- 至少 個連通分支即至多 條邊。最優值為 。當 時,此值為 ,在 時以 取得。
被接受邊的權按接受次序是非遞減的,所以這些最小值很容易找到。對於「至多 個」,先執行 ,然後只要下一條被接受邊的權為負便繼續接受。對於「至少 個」,在達到 條邊時停止,或在第一條權為正的被接受邊之前停止,以較早者為準。權為零的邊可取可不取,不會改變權。
反例模式
恰有 k 個連通分支不等於至多 k 個連通分支
斷言: 輸出的森林,在所有至多有 個連通分支的森林中也是權最小的。取追蹤中的圖與 ,則 , 輸出權為 的 。集合 同樣是森林,它有 個連通分支,權為 。所以 對於「至多五個連通分支」並不最優。定理講的是恰好的個數,因為交換論證把邊數固定為 。修正辦法就是上文對「至多 個」的規則:執行 之後,只要下一條被接受邊的權為負便繼續接受。這裏會接受 (權 ),然後停止,因為下一條被接受邊的權 不是負數,得到 。
7. 複雜度及注意事項
- 初始化: 次 make-set 操作需時 。
- 排序: 按 對 條邊進行比較排序,成本為 。當 時,由簡單圖的性質得 ,所以這亦是 。提早停止並不會減低最壞情況下的排序成本,因為排序在掃描開始前已經完成。當 時,可以略過排序並直接輸出 。
- 併查集: 採用按秩合併及路徑壓縮時,至多 次 find 及 次 union 需時 。若沒有平衡規則,在最壞情況下個別 find 可能需時 。因此上述界限取決於實作方式。
- 總計: :初始化貢獻 ;對於 的連通圖,排序項已涵蓋併查集掃描的成本。單頂點圖沒有邊,需時 。非比較排序(例如對有界整數權使用基數排序)可以做得更好,但不屬於比較模型的範圍。
8. 即時檢查
快速檢查
(在 10 個頂點上的一個森林有 7 條邊。它有多少個連通分支?)
解答 · 答案
由連通分支數引理,它有 個連通分支。
快速檢查
(對追蹤中的圖與 , 輸出甚麼?它的權是多少?)
解答 · 答案
目標為 條邊。掃描接受 、 和 之後停止,輸出 ,權為 ,等於表中的 。
快速檢查
(所有邊的權都是 ,且 。 輸出哪個森林?)
解答 · 答案
目標為一條邊。所有權都相同,所以 就是編號的次序,掃描接受編號為 的邊。輸出為 ,權為 ;第一條被掃描的邊必定被接受,因為單獨一條邊不會形成環。
快速檢查
(每個權都增加 。 的輸出會改變嗎?)
解答 · 答案
不會。次序 不變,所以掃描接受同樣的邊。每個候選森林都恰有 條邊,所以所有權都平移同一個量 ,最小者不變。對「至多 個」的問題這就不成立,因為邊數是變化的。