網絡設計者要用成本最低的一組連線把 個站點連起來,每條可能的連線都有成本。答案就是最小生成樹。兩個經典算法都能構造最小生成樹,兩者的正確性都建基於同一個結構性事實,即割性質。Kruskal 算法還需要一個記錄「哪些頂點已經連通」的數據結構,即不相交集合並查集(union–find)。本節只在比較時提及 Dijkstra 算法的最短路徑想法;主要的先備知識是連通性與遍歷各節的圖論詞彙:連通、圈、樹與連通分量。
1. 生成樹與問題
定義 18.1.1
(生成樹與最小生成樹)
設 為有限、連通的無向圖,有 個頂點,每條邊有實數權重 。允許平行邊;自環永遠無用,予以忽略。生成樹是邊集 ,使 連通且無圈。每棵生成樹恰有 條邊,並且向生成樹加入任何一條非樹邊,恰好產生一個圈。最小生成樹(MST)是總權重 最小的生成樹。權重相同時可能有多棵最小生成樹,但它們的總權重一樣。權重可以為負;只有大小次序重要。
定義 18.1.2
(割、橫跨邊與尊重割的邊集)
割是把頂點分成兩個非空部分 。若一條邊的兩個端點分屬兩部分,就說它橫跨該割。若邊集 中沒有邊橫跨某個割,就說 尊重該割。
2. 割性質
定理 18.1.3
(割性質)
設 ,其中 為某棵最小生成樹。設 是 所尊重的割, 是所有橫跨該割的邊中權重最小的一條。則存在最小生成樹 使 。
證明
(以最輕橫跨邊換走圈上的一條邊)
若 ,取 。否則 恰含一個圈,且它經過 。這個圈從割的一側出發又回到同一側,所以橫跨該割的次數為偶數; 是其中一次,因此圈上還有另一條橫跨的邊 ,且 (圈上除 外的邊都在 中)。因 尊重該割,。由 的選取,。令 。從 中去掉 得到兩個連通分量,而 在 的唯一圈上,所以 的兩個端點屬於不同分量;故 連通且有 條邊,是生成樹。其權重為 ,所以 是最小生成樹,並包含 。
證明透視
割性質各項假設的用處
中有圈,是因為 而 是生成樹。 橫跨該割,加上圈橫跨割的次數是偶數,就得出圈上另一條橫跨邊 。「 尊重該割」只用了一次:它說明 ,所以刪去 不會刪走 的任何邊。 在橫跨邊中最輕這一點也只用了一次:它給出 ,所以交換不會增加權重。最後, 在圈上,所以 把 的兩個連通分量重新接上,結果仍是生成樹。
這是一個交換論證:從任意一個最優解出發,把其中一個元素換成貪心的選擇,而不損失最優性。因此,若貪心算法每一步都加入割性質所認可的邊,就能維持不變量「已選的邊包含於某棵最小生成樹」。
反例模式
「尊重割」的假設不能去掉
聲稱:若 含於某棵最小生成樹,而 是橫跨某個割的最輕邊,則不論 是否尊重該割, 都含於某棵最小生成樹。取頂點 上的三角形,三條邊的權重都是 。那麼 是權重為 的最小生成樹。對割 ,橫跨邊為 與 ,權重都是 ,所以 是橫跨該割的最輕邊。但 含有橫跨邊 ,而 是整個三角形,含有圈,不含於任何生成樹。修正方法是加上「 尊重該割」的假設:此時證明中被刪去的邊 絕不在 內。
3. 不相交集合並查集
定義 18.1.4
(不相交集合並查集)
不相交集合結構維護 的一個劃分,支援 find(x)(返回包含 的集合的代表元;在該集合改變之前,同一集合的所有元素返回相同的代表元)與 union(x,y)(合併兩個集合)。
把每個集合表示為存於陣列 parent 中的有根樹:根 滿足 parent[r]=r 並作為代表元,另為根記錄 size[r]。
make: parent[i] = i; size[i] = 1 for each i
find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
union(x, y):
a = find(x); b = find(y)
if a == b: return false
if size[a] < size[b]: swap a, b
parent[b] = a; size[a] = size[a] + size[b]
return true
引理 18.1.5
(按大小合併限制深度)
若只使用按大小合併,每棵樹的深度至多為 ,所以 find 耗時 。
證明
(深度只在樹大小加倍時增加)
頂點 的深度只會在它所在樹的根被掛到另一個根之下時加一,而這只在 所在樹的大小不超過另一棵樹時發生;合併後的樹大小至少是原先 所在樹的兩倍。一棵樹至多有 個頂點,所以 所在樹的大小至多翻倍 次。故深度至多為 。
路徑減半只會縮短路徑,所以引理的深度上界依然成立。另有一個標準結果(此處引用而不證明):按大小合併加上路徑壓縮或路徑減半,對 個元素執行 次操作的總時間為 ,其中 為反 Ackermann 函數,對記憶體容得下的任何輸入都小於 5。本節把每次操作視為 已足以得出下面的界。
4. Kruskal 算法
sort edges so that w(e_1) <= w(e_2) <= ... <= w(e_m)
T = empty; make the disjoint sets
for i = 1..m:
(u, v) = e_i
if union(u, v): add e_i to T
return T
一條邊被接受,當且僅當它的兩個端點位於當前森林 的不同連通分量。
定理 18.1.6
(Kruskal 算法的正確性)
對連通圖,Kruskal 算法返回一棵最小生成樹。
證明
(每條被接受的邊都是最輕的橫跨邊)
以歸納法證明每一步之後邊集 都包含於某棵最小生成樹。起初 。設邊 被接受,且 ( 為某棵最小生成樹)。令 為 中包含 的連通分量的頂點集,則 。 中沒有邊橫跨 ,所以 尊重此割,而 橫跨它。設 是另一條橫跨此割的邊。若 在排序中較早,它不在 中( 沒有邊橫跨此割),所以它當時已被檢查而被拒絕,表示當時森林已把它的兩個端點連通;森林只會增大,所以它的端點現在仍在同一分量內,但 橫跨該割,矛盾。因此除 外,所有橫跨的邊在次序中都較後,。故 是橫跨該割的最小權重邊,由割性質, 包含於某棵最小生成樹。被拒絕的邊不加入,不變量保持。
結束時 是森林。假設它有至少兩個分量。因 連通, 中有一條邊 連接兩個不同的最終分量。檢查 時,它的端點已在不同分量(分量只會合併),所以 會被接受,矛盾。因此 是包含於某棵最小生成樹的生成樹,即它本身就是最小生成樹。
證明透視
為甚麼被接受的邊是最輕的橫跨邊
不尋常的一步,是從算法的狀態取出一個割:取 為當前森林中 所在的連通分量,於是森林按構造尊重這個割。然後有兩個事實使 成為最輕的橫跨邊。次序已排好,所以較後檢查的橫跨邊至少一樣重。而連通分量只會合併,所以較早檢查的橫跨邊只會在端點已連通時才被拒絕,但橫跨邊的端點從不連通;因此沒有橫跨邊在 之前。最後的論證是獨立的,用到 連通:連接兩個最終分量的邊必會被接受。沒有排好的次序,割論證就甚麼也得不到。
若 不連通,同一算法返回最小生成森林。
複雜度。 排序耗時 ;在沒有平行邊時 ,故為 。 次並查集操作按引理耗時 ,用所引用的結果則為 。總計 ,即沒有平行邊時為 。
概念視角結構
生成樹記錄了每一個門檻
對每個實數 ,令 為頂點集 上只含權重不超過 的邊的圖。Kruskal 檢查完所有這些邊之後,每條被拒絕的邊的端點早已連通,每條被接受的邊都連接了兩個連通分量,所以森林與 有相同的連通分量。因此兩個頂點在 中連通,當且僅當它們之間的樹上路徑的權重全都不超過 :該路徑上最重的邊,就是兩頂點開始連通的最小門檻。在下面的例題中,頂點 與 在 中不連通,在 中連通,而它們的樹上路徑最重的邊正是 。
5. Prim 算法
Prim 算法從根 起生長單一棵樹。維護頂點集 (起初為 )與樹 。反覆選取恰有一個端點在 內的最小權重邊,把它與其新端點加入。
用二叉堆存放候選邊 ,按權重排序:先把 的所有出邊推入;反覆彈出最小者,若 就丟棄,否則把 加入 ,把該邊加入 ,並把 到 之外頂點的所有邊推入。
正確性。 每一步樹邊都在 之內,所以它們尊重割 ;所選的邊是橫跨該割的最小權重邊,割性質維持不變量「 包含於某棵最小生成樹」。加入 條邊後, 是包含於某棵最小生成樹的生成樹。堆中至多有 個項目,所以時間為 ,沒有平行邊時即 。其結構與 Dijkstra 算法相似,但頂點的鍵是單一條連接邊的權重,而不是路徑長度。
6. 例題:Kruskal 與並查集的追蹤
例題 18.1.7
(Kruskal 與並查集追蹤)
頂點 ,邊為 (4)、(1)、(2)、(5)、(8)、(10)、(3)。按權重排序:(1)、(2)、(3)、(4)、(5)、(8)、(10)。大小相同時,union(x,y) 把 的根掛到 的根之下。
- :根為 1 與 3,大小同為 1,打成平手;
parent[3]=1,size[1]=2。接受。 - :
find(2)=2,find(3)=1;2 所在樹大小為 1,小於 2,故parent[2]=1,size[1]=3。接受。 - :平手;
parent[5]=4,size[4]=2。接受。 - :兩個根都是 1。拒絕(它會閉合圈 )。
- :
find(2)=1(大小 3),find(4)=4(大小 2);parent[4]=1,size[1]=5。接受。 - :根相同。拒絕。7. :根相同。拒絕。
最小生成樹為 ,權重 ,共 條邊。
例題 18.1.8
(不連通的圖得出森林)
取頂點 與邊 (1)、(2)。Kruskal 接受 ,因為 find(1) 與 find(2) 不同;同樣地接受 。輸出有 條邊,但 個頂點上的生成樹需要 條。由於沒有邊連接 與 ,這兩個分量永不合併,所以輸出是權重為 的最小生成森林。一般而言, 個頂點、 個連通分量的森林有 條邊,所以接受的邊少於 條,就表示圖不連通。
7. 例題:同一個圖上的 Prim
例題 18.1.9
(同一個圖上的 Prim)
從 開始。
- :橫跨邊 (4)、(1)。選 。
- :橫跨邊 (4)、(2)、(8)、(10)。選 。
- :橫跨邊 (5)、(8)、(10)。選 。
- :橫跨邊 (10)、(3)。選 。
總權重 ,與 Kruskal 得到的是同一棵樹。
8. 常見錯誤
- 把 Kruskal 被拒絕的邊視為錯誤:它們正是端點已經連通的邊。
- 把兩個算法用於有向圖。最小生成樹形圖需要另一種算法。
- 在不連通的圖上執行 Prim 或 Kruskal 並期望得到一棵樹:結果是每個連通分量一棵樹的森林。
常見錯誤
(重用過時的 find 結果)
根會隨著合併而改變,所以為前一條邊算出的 find 結果可能已過時。每條邊在被檢查的當刻都要重新調用 find。
常見錯誤
(以為最小生成樹必定唯一)
當所有權重互不相同時,最小生成樹是唯一的,最後一道練習會證明這一點。有並列權重時未必唯一:三條邊權重都是 的三角形有三棵最小生成樹,每兩條邊一棵,權重都是 。
常見錯誤
(從最小生成樹讀出最短路徑)
最小生成樹使總權重最小,並不使距離最小。對 、、 的三角形,唯一的最小生成樹是 ,其中從 到 的路徑長度為 ,而邊 的長度為 。
練習
練習 18.1.10
(頂點 ,邊 (3)、(1)、(3)、(2)、(4)。求最小生成樹的權重,並列出所有最小生成樹。)
核心
解答(3)
- 1
對排序後的邊執行 Kruskal
排序:(1)、(2),然後是 與 (3),最後是 (4)。Kruskal 接受 與 ,得到分量 與 。下一條邊 或 把它們連起來,所以共接受三條邊,權重為 。
- 2
說明不存在更輕的生成樹
關鍵一步
邊的權重由小到大為 ,所以任何三條不同的邊,權重至少是 。
依據: 每棵生成樹恰有 條邊。
- 3
列出所有最小生成樹
權重 要求邊的權重為 、,再加上兩條權重為 的邊之一。 與 都是樹。所以最小生成樹的權重為 ,最小生成樹恰好是這兩棵。
快速檢查
(從單元素集合 出發,使用按大小合併,平手時把 的根掛到 的根之下,依次執行 union(1,2)、union(3,4)、union(1,3)。給出 parent 陣列與頂點 4 的深度。)
記錄各個根的大小。
解答 · 答案
union(1,2):平手,parent[2]=1,size[1]=2。union(3,4):平手,parent[4]=3,size[3]=2。union(1,3):根為 1 與 3,大小都是 2,平手,parent[3]=1,size[1]=4。頂點 的 parent 陣列為 。頂點 4 經 ,深度為 2,等於 ,即引理的上界。
快速檢查
(在第一道練習的圖(邊 (3)、(1)、(3)、(2)、(4))上從頂點 執行 Prim,並給出總權重。)
列出每一步的橫跨邊。
解答 · 答案
:橫跨 (3)、(1);取 。:橫跨 (3)、(3)、(4);取 或 (平手,取 )。:橫跨 (2)、(4);取 。總權重 ,與 Kruskal 的結果一致。
練習 18.1.11
(證明:若連通圖的所有邊權重互不相同,則其最小生成樹唯一。)
綜合證明
解答(4)
- 1
假設有兩棵不同的最小生成樹,取只屬於其中一棵的最輕邊
設 都是最小生成樹,令 為恰好屬於其中一棵的最輕邊。由於兩者地位對稱,不妨設 。
依據: 權重互不相同,所以這條邊是唯一的。
- 2
找出圈與一條不在 內的邊
集合 含有經過 的圈。這個圈上有一條邊 ,否則圈整個在 內,而 無圈。於是 且 ,所以 恰好屬於其中一棵樹。
- 3
比較權重
關鍵一步
因此 。
依據: 是恰好屬於一棵樹的邊中最輕的,而且權重互不相同。
- 4
交換得出更輕的樹
∎由於 在 的唯一圈上, 是生成樹,其權重為 。這與 是最小生成樹矛盾。