假設連線有成本,我們要連通原網絡中每一對本來能互相到達的頂點。先選便宜的邊似乎合理,但若不檢查結構,可能把邊浪費在一個環上。Kruskal 算法結合兩個想法:依成本非遞減次序考慮邊,再用並查集判斷一條邊是否連接兩個不同分量。
數據結構回答的是結構問題,不是最佳性問題。我們會分別證明所選邊構成需要的森林,以及其總成本最小。這樣亦更容易正確處理不連通圖、同權邊和負成本。
為每種輸入圖指定輸出
令 為有限無向加權多重圖。平行邊是不同輸入邊,允許自環,每條邊的整數權重可以是負數。頂點編為 ,允許 。每條邊都有輸入索引,故同權平行邊仍可區分。
定義 14.1.1
(生成森林與最小成本)
生成森林包含所有頂點、沒有環,且與 有相同的連通分量。因此每個非平凡原圖分量都由一棵樹生成;孤立頂點則是一棵沒有邊的單頂點樹。自環不能屬於森林;在本節的多重圖慣例中,同時選兩條平行邊會形成長度為二的環。
森林的成本是所選邊權重之和。最小生成森林是在所有生成森林中成本最小的一個。若 連通且非空,它就是最小生成樹。當 ,空森林成本為零。
我們不要求輸入連通,也不聲稱最佳解唯一。固定同權邊的次序可令一次實作的結果可重現,但不代表所有最小森林都相同。
先排序,只接納連接不同分量的邊
起初沒有選邊,每個頂點自成一個並查集集合。按 (權重, 輸入索引) 排序邊。依序考慮每條 :比較 find(u) 與 find(v)。根不同便選 並合併集合;根相同則跳過。檢查全部邊後,回傳所選邊及其成本。
自環的兩端是同一頂點,因此即使權重為負也一定跳過。較後的平行邊不是因為「平行」便自動跳過,而是當它被考慮時,若兩端已被所選邊連通才跳過。
常見錯誤
(不做環檢查就取最便宜的邊)
取頂點 0、1、2、3,邊 0–1、1–2、0–2 權重為 1,邊 2–3 權重為 5。最便宜的三條邊就是那個三角形:它含有環,並使頂點 3 與其餘部分斷開,成本為 3。最小生成樹必須使用 2–3 及三角形的兩條邊,成本為 。只數邊數而不檢驗分量,會得出錯誤的答案。
命題 14.1.2
(Kruskal 選出生成森林)
每檢查完一條邊之後,所選的邊構成一個森林,其連通分量恰好就是並查集中的各個集合。掃描結束時,所選的邊是 的一個生成森林。
證明
(所選邊與並查集有相同分量)
起初所選圖沒有邊,並查集都是單點,故兩種分量一致。若一條邊的端點在不同集合,依歸納假設,它們也在不同的所選圖分量。加上該邊會合併兩個分量而不產生環;union 恰好合併相應集合。若兩端已在同一集合,所選邊已提供一條路徑連接它們,再加該邊便構成環。跳過它不改變任一分割。
因此所選邊始終是森林,而每一步 find 恰好代表其連通分量。這證明了環檢查,卻尚未證明權重最小。
掃描結束後,每條原圖邊的兩端都在同一所選分量:被選的邊合併了兩端,被跳過的邊在當時已連通,此後也不會被拆開。每條原圖路徑由這些邊組成,所以其兩端在同一所選分量。反過來,所選邊都是原圖邊,不可能連接不同原圖分量。兩種分量因此一致,結果是生成森林。
概念視角結構
把森林看成邊次序上的規則
Kruskal 的選擇可以不借助程序來陳述:按 這一對把邊排好;邊 被選中,恰好當只用排在它前面的邊找不到連接 與 的路徑。自環永遠不會被選中,因為它的兩端本來就相連。由此可知,輸出只取決於邊的次序,並不取決於權的數值本身:把每個權 換成嚴格遞增的 ,選出的邊完全相同。
貪婪選擇為何能屬於某個最佳解
定理 14.1.3
(Kruskal 的森林成本最小)
對每個有限無向加權多重圖,包括帶有負權、平行邊、自環以及多個連通分量的圖,Kruskal 算法返回的森林都是最小生成森林。
證明
(跨切割交換,同時容許同權及負權)
歸納證明:存在一個最小生成森林 ,包含目前全部已選邊。起初成立,因為有限圖只有有限多個候選森林,所以最佳解存在。
假設算法接下來選 。令 為選 前所選森林中包含 的分量; 在 外。考慮任何跨越此切割的原圖邊 。若 ,算法早已考慮 。它的兩端現在仍在不同所選分量,因為一端在 、另一端在外;分量只會合併,因此當時兩端也不同,算法便會選它,與現在的切割矛盾。所以每條跨切割邊的權重至少是 。
選一個含所有先前已選邊的最佳森林 。若它已有 ,歸納步即成立。否則, 同屬一個原圖分量,故 在該分量的樹中有唯一 – 路徑;路徑必在某條邊 跨越切割。先前已選邊沒有跨越此切割,因為 是所選森林的一個分量,所以刪去 不會失去先前已選邊。在 加入 產生一個環,刪去 後得到另一個生成森林;由 ,成本不會增加。
由於 已是最小成本,新森林也是最佳解,且包含先前已選邊及 。歸納成立。最後所選森林自身已生成原圖各分量,而包含它的最佳森林在各分量也是樹,不能再多含一條邊而不產生環;兩者相同。因此回傳的森林最小。
證明透視
排序在哪裏發揮作用
真正起作用的一步,是對每條跨割的邊 都有 。它依賴兩件事:掃描按權重次序進行,而且分量只會合併,所以較輕的跨割邊早已被接受。交換論證本身只用到 是所選森林的一個分量,因此被移除的邊 以前從未被選過。權重的正負從不出現。若沒有排序,第一件事便不成立,如下面的例子所示。
證明只比較權重,沒有假設權重為正。同權交換可保持成本,因此可能有多個不同最小森林;輸入索引只決定本實作在同權時選哪一個。
反例模式
只做環檢查而不排序並不足夠
取頂點 0、1、2,邊按輸入次序為:0–1 權重 5、1–2 權重 1、0–2 權重 1。依此次序只做環檢查:接受 0–1,再接受 1–2,並因 0 與 2 已連通而跳過 0–2。成本為 。僅由兩條權重為 1 的邊已構成成本為 2 的生成樹,所以結果並非最小。環檢查只保證無環;按 (權重, 索引) 排序,才使每條跨割邊都至少與被接受的邊一樣重。
同權、自環、平行邊和孤立頂點
例題 14.1.4
(不連通輸入仍有明確的最佳森林)
使用頂點 及下表索引邊,其中頂點 4 是孤立點。
| 索引 | 邊 | 權重 | 結果 |
|---|---|---|---|
| 0 | 0–1 | 1 | 選取 |
| 1 | 0–2 | 1 | 選取 |
| 2 | 1–2 | 1 | 跳過:成環 |
| 3 | 1–3 | 3 | 跳過:已連通 |
| 4 | 2–3 | 2 | 選取 |
| 5 | 3–3 | -5 | 跳過:自環 |
| 6 | 0–1 | 4 | 跳過:平行邊會成環 |
按權重及索引處理的次序是 。所選索引為 ,成本是 。最後分量是 與 ,與原圖一致。若同權邊採用另一順序,三條權重 1 的邊中可選不同兩條,成本仍為 4。
例題 14.1.5
(平行邊:較輕的一條勝出)
取頂點 0、1、2 及帶索引的邊:0 號是 0–1 權重 3,1 號是 0–1 權重 2,2 號是 1–2 權重 4,3 號是 0–2 權重 4。處理次序是索引 。選中 1 號邊。0 號邊是平行副本,兩端已連通,所以雖然在輸入中排在前面,仍被跳過。2 號邊把頂點 2 連到 ,被選中;3 號邊會形成環,被跳過。所選索引為 ,成本 。2 號與 3 號邊的並列由索引決定;若改選 3 號邊,會得到另一個成本相同的最小森林。
常見錯誤
(按輸入次序刪去平行邊)
只保留若干平行邊中的第一條並不安全。上例中 0–1 的第一條副本權重為 3,若只用各組的第一條副本建圖,最小森林成本是 ,而用較輕的副本則是 6。平行邊必須全部進入排序。
實作並查集
以下實作使用按大小合併,不做路徑壓縮。每個根儲存其集合大小;非根的大小欄位不必保持最新。find 沿父指標走到根。合併不同根時,較小樹的根成為較大樹根的子節點;大小相等則偏向傳給 union 的第一個根。
class DisjointSets:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, vertex):
while self.parent[vertex] != vertex:
vertex = self.parent[vertex]
return vertex
def union(self, left, right):
a, b = self.find(left), self.find(right)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def minimum_spanning_forest(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
indexed = []
for index, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n:
raise ValueError("edge endpoint outside the vertex range")
indexed.append((weight, index, u, v))
indexed.sort()
sets = DisjointSets(n)
selected = []
cost = 0
for weight, index, u, v in indexed:
if sets.union(u, v):
selected.append(index)
cost += weight
return cost, selected
輸入為非負整數 n 與 (u, v, weight) 三元組的可迭代集合,端點與權重為整數。程式檢查端點範圍,但假設類型及三元組結構符合契約。它另建有索引列表,不修改調用者的邊集合。返回索引代表原輸入邊,次序為貪婪處理次序。n=0 時邊列表必須為空,返回 (0, [])。
命題 14.1.6
(按大小合併使父鏈保持短)
使用按大小合併而不做路徑壓縮時,在 個頂點上,每次 find 至多沿 條父連結前進,所以 find 與 union 各需 步。
證明
(按大小合併為何令父鏈不長)
每當一個根變成子節點,其整棵樹不大於新夥伴。於是深度增加的每個頂點,其所在集合至少增至原本兩倍。頂點由單點集合開始,集合最多有 個頂點;當 ,其深度最多增加 次。
因此 find 和一次 union 使用 個父鏈步驟。此簡單界不依賴路徑壓縮定理。大小指合併時的整個集合;過時的非根大小不會用來選擇新父節點。
對 條輸入邊,建立索引與初始化需 ;比較排序需 。 次合併嘗試共需 ,因此總時間為
額外空間為 ,包括索引列表及輸出。這是操作數界;任意大小整數的比較與加法另有位元成本。配合路徑壓縮的進階並查集可有更精確的攤銷界,但並非此程式所實作的方法。
例題 14.1.7
(四個頂點上的按大小合併,及最小輸入)
在四個頂點的圖上依次處理邊 0–1、2–3、0–2。union(0,1) 連接大小相等的根 0 與 1,所以根 1 成為 0 的子節點,size[0] 變為 2。union(2,3) 使 3 成為 2 的子節點。union(0,2) 比較相等的大小 2 與 2,所以根 2 成為 0 的子節點,size[0] 變為 4。最深的頂點是 3,深度為 2,與 吻合。
在最小的輸入上, 且沒有邊時,函數返回 (0, []); 且只有一條權重為 的自環時也是如此,因為 union(0,0) 找到相同的根而返回 false。
練習與解答
快速檢查
(1. 為何負權自環會被跳過,即使它可以減少所選邊的權重和?)
解答 · 解答 1
生成森林必須無環,而自環本身就是環。其兩端是同一頂點,union 返回 false,Kruskal 因此跳過它。目標是在合法生成森林中最小化成本,不是在任意邊子集中取最小總和。
快速檢查
(2. 五頂點例子的所選邊索引和最後分量是甚麼?孤立頂點會令結果無效嗎?)
解答 · 解答 2
所選索引是 [0, 1, 4],總成本 4;分量為 和 。孤立頂點保留為單頂點樹,結果是最小生成森林,而不是整個不連通圖的一棵生成樹。
快速檢查
(3. 三個頂點的 0–1、1–2、0–2 權重皆為 1。最小生成樹唯一嗎?)
解答 · 解答 3
不唯一。任選兩條邊都連通三個頂點、沒有環,總成本為 2。確定的輸入索引次序會選出其中一個最佳解,但不會消除其他有效最佳樹。
快速檢查
(4. 為何被跳過的邊不必重新考慮,仍能保證最後生成原圖各分量?)
解答 · 解答 4
邊被跳過時兩端已在同一所選分量。之後合併只會合攏分量,不會拆分,所以兩端持續連通。最後每條原圖邊、因而每條原圖路徑的兩端均在同一所選分量;所選邊又不能連接不同原圖分量。
貪婪證明與數據結構證明各有工作:交換論證證明權重最小;並查集不變量令環判斷有效率。只檢查其中一個,不能取代另一個。