動機
最小生成樹(minimum spanning tree)以總權重最小的邊,把無向加權圖的所有頂點連通起來。Kruskal 算法在全局範圍內挑選邊,逐步生長出一片森林。Prim 算法則從選定的根出發只生長一棵連通的樹,每一步都加入一條由樹連向未訪問頂點的最便宜的邊。其正確性來自一個割上的交換論證,而高效的實作則為每個樹外頂點維護目前已知的最便宜連接。
邊權可以為負,也可以相等。與最短路徑算法不同,Prim 算法的鍵(key)是某一條跨越邊的權重,而不是由根出發的路徑長度。儘管兩種算法都可以使用優先隊列,這個區別仍然十分重要。
定義
定義 3.7.1
(生成樹與割)
設 為有限連通無向圖,,邊權為實數。生成樹是包含每個頂點的、連通且無圈的邊集。對於非空真子集 ,若一條邊的一個端點在 中而另一個端點在 外,則稱該邊跨越(crosses)這個割。
定義 3.7.2
(Prim 算法)
Prim 算法從屬於 的一個根出發,此時尚未選取任何邊。當 時,選取一條跨越割 的權重最小的邊,把這條邊加入已選邊集,並把它在 外的端點加入 。權重相等時可以任意取捨。在連通圖中,只要 非空且不等於 ,這樣的邊就一定存在。
定理
定理 3.7.3
(Prim 算法是正確的)
對於每個連通加權無向圖,Prim 算法都會終止並輸出一棵最小生成樹,即使邊權為負或存在相等的權重也是如此。
定理 3.7.4
(附索引的二元堆積實作)
使用鄰接表和支援 extract-min 與 decrease-key(兩者均為 時間)的附索引二元最小堆積,當 時,Prim 算法的執行時間為 ,空間為 。
證明思路或證明
證明
(Prim 的不變量給出最小生成樹)
維護以下不變量:已選取的邊在 上構成一棵樹,並且被包含在某棵最小生成樹 中。起初已選邊集為空,不變量成立。設 是跨越目前割的一條最小邊。若 ,則同一棵最小生成樹說明加入 之後不變量依然成立。否則,把 加入 會產生唯一的一個圈。 中連接 兩個端點的路徑跨越該割,所以這個圈中還含有另一條跨越邊 。已選取的邊全部位於 之內,因此 不是已選邊之一。由於 ,以 取代 得到一棵權重不大於 的生成樹。由 的最小性,它同樣是一棵最小生成樹,並且包含擴大後的已選邊集。
加入一條通向一個新頂點的邊,會保持已選子圖的連通性與無圈性。每次迭代使 增加一,所以加入 條邊之後,它就是一棵生成樹。由不變量,它被包含在某棵最小生成樹中;兩者都有 條邊,故相等。這個證明只用到邊權之間的比較,因此對負權與相等權重同樣成立。
證明透視
安全邊保持了最優性
這個交換並不宣稱所選的邊屬於每一棵最小樹,它只是構造出一棵包含此前所有選擇以及新邊的最小樹。論證依賴三件事。 的兩個端點之間的樹路徑必定跨越這個割,不論權重如何,都因此得到一條可替換的邊 。每條已選的邊的兩個端點都在 內,所以 不是已選的邊,刪去它保留此前所有的選擇。最後,,因為 是跨越該割的最輕邊,所以交換不會使權重增加。只有這一次比較涉及權重,這就是為甚麼負權或相同的權重都不構成困難。若 不是最輕的,交換可能使權重增加,不變量就會失效。
證明
(堆積中的鍵是最輕的跨越邊)
對於堆積實作,為每個在 之外的頂點維護一個鍵,其值等於目前已知的由 到該頂點的最輕邊的權重,同時維護一個父端點來見證這個鍵。根的鍵起初為零,其餘所有鍵均為無限大。每當一個頂點被取出,就掃描它的鄰接表,只要新的跨越邊更輕,就降低相應鄰居的鍵。對被取出的頂點個數作歸納可知,每個有限的鍵都等於由目前的 到該樹外頂點的所有邊的權重的最小值。因此最小鍵給出一條全局最輕的跨越邊。
共有 次取出操作,且每條無向邊最多被鄰接表檢查兩次。成功的鍵降低至多發生 次。每次堆積操作耗時 ,而圖與堆積的儲存為 。二元堆積的高度為 ;extract-min 與 decrease-key 只沿至多一條由根至葉的路徑恢復堆積順序。由於圖連通,每個被取出的非根頂點都有一個有限的、附見證的鍵。
例題詳解
例題 3.7.5
(生長一棵樹)
對於權重為 、、 的三角形,從 出發。最輕的跨越邊是 ,然後由 連向 的最輕邊是 。所得的樹權重為 。
例題 3.7.6
(一條負權邊)
對於三邊權重為 的三角形,Prim 算法可以先選取負權邊。其交換證明依然適用:最小生成樹是使總權重最小的生成樹,而證明中從未用到權重非負的假設。
例題 3.7.7
(出現相等權重並不表示樹唯一)
在三條邊權重都是一的三角形中,任意兩條邊都構成一棵最小生成樹。不同的取捨方式可能返回不同的樹,它們的總權重都是二。
常見錯誤
反例模式
Prim 的鍵不是路徑距離
在邊權為 和 的路徑 中,加入 之後, 的 Prim 鍵是 ,即邊 的權重。而由 到 的最短路徑距離是 。把鍵當作路徑距離,就混淆了兩個不同的目標。
常見錯誤
(連通性與優先隊列的更新)
按所述方式執行的單棵樹算法需要圖是連通的。在非連通圖上,在所有頂點都被到達之前,割可能沒有任何跨越邊;在每個連通分量中重新開始可以得到一個生成森林,但這需要另行規定輸出的要求。優先隊列必須以與目前鍵一致的方式支援更新;若採用另一種容許過期項目存在的實作,則需要單獨分析其正確性與複雜度。
割交換的詳細論證
這個不變量是存在性的:每一步之後,至少存在一棵包含所有已選邊的最小生成樹。權重相等可能表示存在多棵最小生成樹,而新選出的邊不必屬於所有這些樹。交換論證足以在不假設唯一性的情況下保留一棵合適的最優樹。
當一條邊 連接 中的一個頂點與 外的一個頂點時,把它加入生成樹 會產生唯一的一個圈。這是因為樹中兩個端點之間本來就有唯一的路徑;這條路徑加上 就是那個圈。該路徑從 之內出發,終止於 之外,所以它至少含有一條跨越該割的邊 。去掉 就打破了這個圈,並留下一棵連通的生成樹。已選取的邊的兩個端點都在 中,所以它們都不可能是這條跨越邊。因此這次替換保留了此前所有的選擇。
如果 與 權重相等,新樹的權重與原樹完全相同。如果 嚴格更輕,新樹就會比假定的最小樹更輕,這是不可能發生的;而這個不等式已經足以證明存在一棵包含 的最小生成樹。這一推理即使某些權重為負也同樣適用。生成樹的邊數是固定的,並且不能重複使用同一條負權邊,所以最短路徑(walk)中出現的負環問題與此處無關。
例題 3.7.8
(最小生成樹不必保持最短路徑)
取三角形,、、。從 出發的 Prim 算法先選 ,再選 ,得到權重為四的最小生成樹。該樹中由 到 的路徑權重為四,而原圖中的最短路徑是權重為三的直接邊 。樹的最小總權重與由根出發的最短距離是不同的目標。
維護堆積的不變量
在根被取出之前,它的鍵為零,其餘每個頂點的鍵均為無限大。根不選取任何邊。取出一個頂點 之後,把它加入 ,並掃描與它關聯的邊。對於每個仍在 之外的鄰居 ,把邊權 與 的目前鍵作比較。若前者更小,就更新該鍵,並記錄 為其父節點。權重相等的邊不必取代原有的父節點:原有的邊仍然是一個合法的跨越邊見證。
假設在加入 之前,每個樹外鍵都等於由舊的 到該頂點的邊的最小權重。加入 之後,新增的跨越邊候選只有與 關聯的邊。掃描它們並取最小值就恢復了不變量。因此,所有樹外頂點中最小的鍵就是所有跨越邊中最小的權重,其父邊是 Prim 算法的一個合法選擇。這既解釋了堆積為何能實作抽象的算法,也說明了如果沒有鍵的不變量,僅僅取出數值標籤最小者是不足夠的。
附索引的堆積對每個樹外頂點最多保留一個有效的堆積項目,並記錄其位置,使 decrease-key 能夠找到它。執行 extract-min 時,以最後一個項目取代根項目並將其向下移動,可沿一條高度為 的路徑恢復堆積順序。decrease-key 則沿至多一條這樣的路徑把被改變的項目向上移動。透過插入 個初始項目來建堆積需要 時間,在所述界限之內;線性時間建堆積也是可行的,但本分析並不需要。
每條無向邊都出現在其兩個端點的鄰接表中。隨著頂點進入 ,它至多被檢查兩次,所以共有 次檢查,成功的鍵降低次數也至多如此。加上 次取出操作,當 時,堆積操作耗時 。堆積和每個頂點的陣列佔用 空間,鄰接表佔用 。當 時,算法立即返回空邊集。
非連通圖與約定
如果圖是非連通的,把目前連通分量與其他所有分量分隔開的割可能沒有任何跨越邊。一個設計為返回最小生成森林的版本,可以在每完成一個連通分量時,從一個未訪問的頂點重新開始 Prim 算法。對每個連通分量分別運用連通圖情形的證明可知,它們的聯集是一個最小生成森林,這裏最小生成森林定義為在每個連通分量中都是最小生成樹。這與單棵生成樹是不同的輸出要求。
只要每條平行邊都被檢查並計入 ,平行邊就是無害的;最便宜的一條可以成為鍵的見證。自環永遠不跨越任何割,也不可能屬於生成樹,所以可以忽略。如果輸入的表示中含有自環,鄰接表掃描必須避免把它當作通向樹外頂點的邊。這些約定不影響交換證明。
對於只有一個頂點的連通圖,空邊集是它唯一的生成樹,總權重為零。對於含有若干孤立頂點的非連通圖,生成森林對每個頂點各有一個單點分量,且沒有邊。明確說明這些邊界情形,可以避免堆積實作試圖為根加入一條父邊。
比較算法的保證
Prim 與 Kruskal 都使用安全邊論證,但它們目前維護的結構不同。Prim 維護一個連通集 ,並在它的割上作選擇;Kruskal 維護一片森林,按全局的權重順序考慮各條邊,並拒絕會產生圈的邊。兩種算法都不要求所有權重互不相同。不同的取捨方式可能產生不同的最小生成樹,所以在存在相等權重時,比較邊的列表不是可靠的正確性檢驗;應當比較總權重,並驗證樹的性質,或使用合適的證書。
最小生成樹優化的是所選邊之和。如三角形的例子所示,它不一定使由根至各頂點的路線最短。Dijkstra 算法維護的是暫定路徑長度,其假設與不變量都不同。共用最小堆積並不表示這兩種鍵的含義可以互換。
常見錯誤
(有效的生成樹不一定是最小的)
對一次有限的執行,可以透過確認它選取了 條邊、沒有圈且連通所有頂點來檢查其基本有效性。這些條件證明的是它是一棵生成樹,而不是最小的。最優性由 Prim 各步選擇的交換證明提供。對於另行給出的一棵樹,則需要額外的最小樹證書或比較算法才能確立其最優性。
驗證給定生成樹及其唯一性
假設有人給出一棵生成樹 ,但沒有說明它如何得到。對每條端點不同的非樹邊 ,記 為 中連接兩端點的唯一路徑。加入 後,這條路徑和 一起形成一個圈。可以檢驗以下條件:
這個條件是 為最小生成樹的充要條件,權重相等或為負數也適用;自環不屬於任何生成樹,可忽略。若不存在非樹、非自環邊,條件自動成立,而且 是唯一的生成樹。
定理 3.7.9
(最小生成樹的圈證書)
生成樹 是最小生成樹,當且僅當對每條非樹、非自環邊 ,都有 。當且僅當每個這樣的不等式都嚴格成立時, 才是唯一的最小生成樹。
證明
(證書刻畫最小樹與唯一性)
必要性:若某條 比路徑上的某條邊 更輕,加入 、移除 就得到更輕的生成樹。充分性:任取生成樹 。若 ,取 ,從 移除 得到一個割。 中連接 兩端的路徑必定跨越此割,取其中一條跨割邊 。 是 唯一的跨割邊,所以 ,而 中連接 兩端的路徑必含 。由上述條件,。在 中用 取代 ,得到一棵權重不增加、且與 多一條共同邊的生成樹。重複這個過程直到得到 ,便知對任意 都有 。
同一論證還給出唯一性: 是唯一最小生成樹,當且僅當上述比較全部嚴格。若某條非樹邊 與路徑上的最大權邊 等重,交換它們便得到另一棵同權生成樹。反過來,若比較全部嚴格,對任意 ,上述第一次取代就嚴格減輕權重。因此邊權互異足以保證唯一,但並非必要條件。
例題 3.7.10
(權重相等時的最優性檢驗)
在三角形中令 、,並取 。唯一的非樹邊是 ;它的樹路徑上最大邊權為 ,嚴格小於 。所以 是唯一的最小生成樹,儘管兩條邊權相等。若改為 ,就可用 取代任一條路徑邊,得到另一棵最小生成樹。若改為 ,條件不成立,用 取代 會使總權重從 降至 。
使用此檢驗前,必須先確認 是生成樹;單靠路徑比較不能證明連通和無圈。每次重新遍歷樹來求路徑最大值,是直接的多項式時間方法;更快的數據結構需要另行分析。
總結
Prim 算法利用目前割上的一條最輕邊來生長一棵連通的樹。交換論證維持了它與某棵最小生成樹的相容性。附索引的堆積為每個樹外頂點維護最便宜的跨越邊,並給出所述的鄰接表複雜度。
練習
快速檢查
(在含有 個頂點的連通圖上,Prim 算法加入多少條邊?)
每加入一條邊就帶進一個新頂點。
解答 · 答案
它加入 條邊,即根之外的每個頂點各對應一條。
快速檢查
(負權邊會使割交換證明失效嗎?)
證明對權重作了哪一個比較?
解答 · 答案
不會。證明只用到所選的跨越邊不比被交換掉的跨越邊更重。
快速檢查
(一個頂點的 Prim 鍵代表甚麼?)
它是路徑長度,還是單條邊的權重?
解答 · 答案
它是由目前的樹到該樹外頂點的單條邊的已知最小權重。
快速檢查
(為甚麼在連通圖上,終止之前必然存在一條跨越邊?)
缺少跨越邊對路徑意味著甚麼?
解答 · 答案
如果某個非空真子集沒有任何邊跨越,那麼由該子集到其補集就沒有路徑,這與圖的連通性矛盾。
練習 3.7.11
(一個圖有樹邊 ,權重依次為 ;非樹邊 的權重依次為 。 是否最小?是否唯一?若有另一棵最小樹,請寫出。)
核心
對每條非樹邊使用圈證書。
解答(3)
- 1
比較 與它的樹路徑
關鍵一步
從 到 的樹路徑是 ,最大權重為 ,而 。這個比較以等號成立。
依據: 非樹邊的權重必須不小於其樹路徑上最重的邊。
- 2
比較 與它的樹路徑
從 到 的樹路徑是 ,最大權重為 ,而 。
- 3
得出最小性與唯一性
兩個不等式都成立,所以 是最小的。 處的等號容許用 取代 ,得到 ,這是另一棵總權重同為 的生成樹。因此 是最小的,但不唯一。