動機
要把多個地點連起來,可以選擇一組無向線路,使線路總成本盡量小。從某個起點到每個地點都最便宜的一組路徑,未必給出總成本最低的網絡:網絡問題選擇的是共享邊集,每條選中的邊只計一次。
兩種貪心算法按不同次序建網。Kruskal 按權重掃描所有邊;Prim 則逐步擴大一個連通區域。兩者共用一個關鍵解釋:跨越合適割的最輕邊,可以透過交換放進一個最優解而不增加成本。邊權相等或已經選過一些邊時,「合適」這一條件尤其重要。
定義與範圍
定義 5.4.1
(生成森林與最小生成森林)
令 為有限無向多重圖,有 個頂點和 個各自具有身份的邊。允許平行邊和自環。每條邊有有限實權,權可以為負、為零或相等。生成森林包含所有頂點,並在 的每個連通分支上限制為一棵生成樹。孤立頂點貢獻單點樹,不貢獻邊。最小生成森林是在這些森林中總邊權最小的一個。若 非空且連通,它就是最小生成樹(MST)。當 時,空森林總權為零;我們不把空圖稱作連通。
定義 5.4.2
(割、跨割邊與尊重)
割由非空真子集 及其補集指定。邊的兩個端點分別在兩側時,它跨越該割。若森林 沒有邊跨割,就說該割尊重 。自環不跨任何割,也不能屬於森林。一個圈可以由兩條不同平行邊構成;提到圈或邊時,都需保留邊的身份。
有限圖存在生成森林,例如在每個分支取一棵生成樹。邊子集只有有限多個,因此至少存在一個最小生成森林。這個存在性論證也適用於任意有限實權,無需非負假設。
定理 5.4.3
(尊重已有選擇的割上最輕邊安全)
設森林 包含在某個最小生成森林中。若一個割尊重 ,且邊 在所有跨割邊中權最小,則存在一個最小生成森林包含 。允許同權;結論是存在包含所選邊的最優解,而不是每個最優解都包含它。
割交換證明
證明
(沿 產生的圈交換)
取包含 的最優森林 。若 已在 中,無需交換。否則 的端點位於原圖同一個連通分支, 在該分支的樹中有連接兩端點的唯一路徑。這條路徑必跨越該割。加入 後得到由路徑和 構成的圈;從其餘圈邊中再選一條跨割邊 。
由於割尊重 ,邊 不在 中。刪去 破圈後,該原分支仍有一棵生成樹,其餘分支不變。由於 是最輕跨割邊,。新生成森林包含 ,權不超過最優森林 ,因此它也是最優的。證明允許平行邊和同權,從未假設最優解唯一。
證明透視
交換必須保留先前選擇
證明只做一次交換,而每個假設控制新森林的一個不同性質。 的兩端點位於割的兩側,迫使它們之間的 -路徑含有一條跨割邊 ;這是割本身被用到的地方。從 與該路徑構成的圈中刪去一條邊,分支仍連通且無圈,所以結果仍是生成森林;這只需要 在圈上。
在跨割邊中最輕,給出 ,所以成本不上升。最後,割尊重 保證 ,因此先前每次選擇都在交換後保留。缺少最後這一性質,交換便可能刪去 中的邊,Kruskal 與 Prim 所用的歸納就會失去其不變量。同權只把嚴格改進變為不增加,而結論只需要不增加。
定理 5.4.4
(圈上的排除與同權)
若一條邊嚴格重於某個圈上的所有其他邊,它不屬於任何最小生成森林。更一般地,圈上一條最大權邊即使與其他邊同權,也至少有一個最小生成森林不使用它。
證明
(以跨越分割的邊替換圈邊)
對於兩條結論,假設某個最優森林含所指定圈邊 。刪除 後,其所在樹分為兩側。原圈的其餘部分有一條邊 跨越這個分割。它不在原樹中,因為一棵樹刪除 後沒有其他樹邊跨越該分割。以 替換 後仍是生成森林。若 嚴格更重,總權下降而矛盾;若 只是最大權,新森林不更重,因而也是不含 的最優解。同權最大邊仍可能出現在另一個最優解中。
Kruskal:按權重擴展森林
按非遞減權重排序所有邊身份,同權次序任取且固定。初始不選邊。依次掃描排序後的邊;僅當邊的端點位於當前已選森林的不同分支時選取它。自環自動被丟棄。繼續直至所有邊都已檢查。
定理 5.4.5
(Kruskal 算法的正確性)
對每個有限加權多重圖及任何固定的同權次序,Kruskal 算法選出的邊構成一個最小生成森林。
證明
(已選森林始終包含在某個最優解中)
選出的邊始終無圈:連接兩個不同森林分支的邊不可能閉合圈。在接受 前,取其一個端點所在當前森林分支的頂點集為 。該割尊重已選森林。任何更輕的跨割邊早已掃描;它當時不可能被拒絕,因為分支只會合併,而它的端點到現在仍分離。因此不存在更輕跨割邊, 是最輕跨割邊。割定理保證「已選森林包含在某個最優森林中」的不變量繼續成立。
掃描結束時,沒有原圖邊連接兩個不同的已選森林分支:這樣的邊在檢查時會被選取,或其端點屆時早已合併。因此已選森林在每個原分支上都生成一棵樹。它包含在一個最優森林中,且已生成每個分支,所以它本身就是最優森林。
並查集可支持分支判斷。按大小合併且不壓縮路徑時,每條父指針鏈長度為 :每次根接到另一根下,其分支大小至少翻倍。比較排序與這些操作合計使用 次比較與索引操作,儲存包括輸入共 。更快的並查集界需要另行分析。這裏假設權重比較精確且每次費用為常數;任意二進制權重表示另有位成本。
概念視角結構
把森林看成擬陣的獨立集
若一個邊集不含圈(環邊除外),便稱它為獨立的。森林的子集仍是森林。若 、 都是森林且 ,則在同一頂點集上 的連通分支較少,所以 有某條邊連接 的兩個分支,可以加入 。這兩個性質使森林成為一個擬陣的獨立集,其極大成員正是生成森林。Kruskal 就是擬陣上的貪心算法,而這個擴充步驟正是上面的交換論證。
Prim:擴展區域,再重新開始
在原圖的一個連通分支任選起點。設 為當前已到達頂點, 為已選邊。只要存在從 到其外側的邊,就添加一條最輕跨割邊及它的外側端點。已選邊始終是 上的一棵樹,該割尊重這些邊。交換定理保持「某個最優森林包含全部已選邊」。沒有跨割邊時, 恰好是整個原連通分支。
圖不連通時,在任意尚未到達的頂點重新開始,對其分支執行同樣規則。所得各樹的並是一個生成森林,且包含在某個最優森林內,因此自身最優。孤立頂點不需要邊。同權可任意打破,並可能得到不同的有效森林。
一種直接實現為每個未到達頂點維護一條已知的、來自當前到達區域的最便宜邊。陣列掃描選擇最小有限鍵;沒有有限鍵時,在未到達頂點重新開始。每個新到達頂點的鄰接表掃描一次。對全圖,初始化及陣列掃描用 ,查邊用 ,包含輸入的儲存為 。鍵是單條跨割邊的權,不是路徑長度。無窮大用獨立的「無候選」標記表示;負邊不會造成問題。
檢查整個候選森林的證書
定理 5.4.6
(路徑最大權的最優性判據)
設 是 的一片生成森林。它最小,當且僅當對於每條不在 中的非自環邊 ,其權至少是兩端點之間唯一 -路徑上邊權的最大值。
證明
(必要性用一次交換,充分性用反覆交換)
必要性:加入一條森林外邊 。如果它比路徑上某條邊更輕,就可用 替換該路徑邊,得到更便宜的生成森林。平行邊同樣適用;排除自環是因為其端點間路徑為空,且自環不能改進森林。
充分性:設顯示的不等式成立,任取一個生成森林 。若它不同於 ,選 。從 的相應樹中刪去 ,把原分支分成兩部分。向 加入 得到一個圈,圈中剩餘路徑必跨越這個分割;取路徑上一條這樣的邊 。除 外, 中沒有邊跨越該分割,所以 。 兩端在 中的路徑含 ,由假設得 。在 中以 換 不增加總權,而且增加它與 的共同邊數。有限次重複後森林變成 。因此 的權不超過任何競爭森林,它就是最小的。
這是可檢查的刻畫,並不自動給出線性時間驗證器。直接實現可以先檢查生成森林性質,再對每條森林外邊遍歷樹路徑;在直接的鄰接表模型下使用 次基本操作。更快的路徑最大值數據結構屬於另一算法問題。判據也適用於負權:應取非空路徑上真正的最大值,不能把初始最大值設為零。
例題
例題 5.4.7
(次序不同,最優結果相同)
取頂點 ,邊權為 、、、、。Kruskal 依次選 、、,總權 。從 開始的 Prim 依次選 、、,總權相同。Kruskal 的首邊不必接觸 Prim 的起點,負權也是允許的。
例題 5.4.8
(同權帶來多棵最優樹)
一個四邊圈的四條邊權都為一,刪去任意一條邊都得到權為三的最小生成樹。某條所選邊可以是某個割上的最輕邊,卻不必屬於每個最優解。如果再加一條權為二的對角線,它在包含它的任一三角圈上都嚴格最重,因此不屬於任何最小生成樹。
例題 5.4.9
(斷開圖與平行邊)
設 之間有兩條權分別為 、 的平行邊, 為孤立頂點, 處有權 的自環。最小生成森林使用權為 的邊,把 作為單點,並忽略自環和較重的平行邊。總權為 。負自環雖然能降低不受約束的邊權和,也不允許選入森林。
反例模式
最短路樹未必使網絡總權最小
取三角形,邊權 、、。從 到兩點都取直接邊可得到最短路樹,其總權為四。最小生成樹使用 與一條權為二的邊,總權為三;但從 到另一端的路徑成本為三,所以它不是以 為源的最短路樹。
常見錯誤與範圍
常見錯誤
(割上最輕邊未必屬於每個最優解)
有同權時,不要斷言每條割上最輕邊都屬於每個最優解。在四條邊權都為一的四邊圈中,每條邊都是某個割上的最輕邊,但刪去該邊所得的生成樹就不含它。
常見錯誤
(不尊重先前選擇的割)
聲稱先前所有選擇均可保留時,不要把尊重已有森林的割換成任意割。在 、 的三角形中,森林 包含在最小生成樹 中。割 不尊重 ,而 是跨越它的最輕邊之一,但 的權為 ,而每棵最小生成樹的權都是 。
常見錯誤
(在斷開圖上只運行一次 Prim)
對於斷開圖,若 Prim 只運行一次,就只得到一個分支的樹,而非全圖生成森林。自環即使為負也不能選:它從不跨越任何割,所以 Prim 永遠不會把它當作候選。
以上權重比較都是精確的。我們不聲稱浮點穩健性、特定堆實現或最短路保證。按邊權總和優化的網絡,與固定源點最短距離是不同目標。
小結
割交換引理安全擴展一個部分最優選擇;圈上嚴格最重邊則不可能出現。Kruskal 與重新啟動的 Prim 按不同次序使用這些事實,都給出最小生成森林。路徑最大值條件獨立刻畫最優性,其驗證實現成本需另行說明。
練習
快速檢查
(對第一個例題中的加權圖運行 Kruskal 和從 出發的 Prim,寫出各自選邊與總權。)
解答 · 答案
Kruskal 依次選 、、;從 開始的 Prim 依次選 、、。兩者總權均為 。Prim 的每一步都選當前到達割上最輕的邊,即使新暴露的 是負邊也無妨。
快速檢查
(三角形三條邊權為一、二、二。找出所有最小生成樹,並解釋圈規則對任一權為二的邊能推出甚麼、不能推出甚麼。)
解答 · 答案
每棵最小生成樹由權一的邊和兩條權二的邊中的恰好一條組成,總權為三。每條權二的邊都在某個最小生成樹中缺席,也在另一個中出現。它們都不是嚴格重於圈上所有其他邊,所以嚴格排除規則對二者都不適用。
快速檢查
(三角形邊權為 、、。由 與 構成的樹是否最小?使用路徑最大值判據;若失敗,給出更便宜的樹。)
解答 · 答案
從 到 的樹路徑經過權為 的 和權為 的 ,最大值為 。但森林外邊 的權為 ,更小,因此判據失敗。用 替換 ,得到總權 ,而原樹為 。若把路徑最大值初始化為零,會錯誤計算這條全負權路徑。
快速檢查
(一個圖有兩個非平凡連通分支,大小分別為三和二,另有一個孤立頂點。生成森林必須有多少條邊?重新啟動的 Prim 如何處理孤立頂點?)
解答 · 答案
三頂點樹有兩條邊,二頂點樹有一條,孤立頂點沒有邊,所以每片生成森林都有三條邊。Prim 在孤立頂點重新開始時找不到跨割邊,該單點分支立即完成。