5.2 最小生成樹：Prim 與 Kruskal

動機

假設要用電纜連接多個地點。若要求只是任何地點都能到達其他地點，便不一定要從某個 指定起點分別鋪設最短路線；不同路線可以共用部分連線，從而降低整個網絡的建造總成本。 這正是最小生成樹（minimum spanning tree，MST）要處理的問題。

本節最重要的分別，是局部便宜不等於全局最優。某條邊的權重很小，不代表可以不加判斷 地選它；若把所有便宜邊都加入，可能會形成環。環代表連線有冗餘，因為刪去環上的其中 一條邊後，環內的頂點仍然連通。Prim 和 Kruskal 都是貪心演算法，但它們並非只說「每次 取最輕的邊」。兩者各自界定目前哪些邊合資格，並拒絕會破壞樹結構的邊。

以下設 G=(V,E) 是有限、非空、連通、無向的加權圖，每條邊 e 有實數權重 w(e)。連通性是必要假設：不連通的圖不可能有包含全部頂點的一棵樹。權重不必互異， 也不必非負；相同權重可能令同一張圖有多棵形狀不同、總權重相同的 MST。

定義

定義

樹與生成樹

樹是連通而且沒有環的無向圖。G=(V,E) 的生成樹是子圖 T=(V,E_T)：它保留 G 的全部頂點，所選邊集合 E_T 是 E 的子集，並且 T 本身是一棵樹。

只有一個頂點的圖以空邊集合為生成樹。若 G 不連通，就不存在生成樹；此時最多只能 得到生成森林（spanning forest），每個連通分量各有一棵樹。

定義

最小生成樹

生成樹 T 的權重是

$$w(T)=\sum_{e\in E_T} w(e).$$

若 T 的總權重不大於 G 任何其他生成樹的總權重，T 就是最小生成樹。 「最小」比較的是所選邊的權重總和，不是邊數；因為所有生成樹本來就有相同邊數。

定義

切割、跨越邊與安全邊

一個切割（cut）把 V 分成兩個非空集合 S 和 V\setminus S。若一條邊的 兩個端點分處兩邊，它便跨越該切割。若目前森林 F 沒有任何已選邊跨越切割，就說該 切割尊重 F。

若把邊加入 F 後，仍然存在某棵 MST 包含全部已選邊，這條邊對 F 就是安全邊。 安全不只表示「暫時沒有成環」；它把避免環與最終的全局最優性連起來。

MST 也不同於最短路徑樹。最短路徑樹先指定源點 s，要求樹中由 s 到每個 可達頂點的路徑都保留原圖中的最短距離。MST 沒有指定源點，只最小化樹邊的總和。 因此，MST 內兩點之間的路徑未必是原圖中的最短路徑。

定理 / 命題

定理

樹的邊數

任何頂點集合為 V 的樹都恰有 |V|-1 條邊。因此，只要一個生成子圖連通、無環， 並已有 |V|-1 條邊，它就是完整的生成樹。反過來，連通而且有 |V|-1 條邊的無向圖 必定是一棵樹。

這個事實給兩種演算法明確的停止條件。在接受 |V|-1 條邊以前，結構仍是一個森林； 若再多接受一條邊，就必定形成環。

定理

最輕跨越邊的安全原則

設森林 F 包含於某棵 MST，而某個切割尊重 F。在所有跨越該切割的邊之中，若 e 的權重最小，則 e 對 F 是安全的：存在一棵 MST 同時包含 F 的全部邊和 e。

Prim 把這個原則用於「已進入目前樹的頂點」與「尚未進入的頂點」之間的切割。 Kruskal 則把它用於目前森林其中一個連通分量周圍的切割。兩者合資格邊的定義不同， 但背後保證最優性的理由相同。

證明思路

先證樹的邊數。對頂點數作歸納：一個頂點的樹有零條邊。任何至少有兩個頂點的有限樹 都有葉節點。刪去一個葉節點和與它相連的唯一一條邊後，餘下圖仍是一棵樹，只是少了 一個頂點。按歸納假設它有 |V|-2 條邊；把刪去的邊放回，便得到 |V|-1 條邊。

再證安全邊原則。設 MST M 已包含 F。若 M 本身已有 e，就毋須改動。 否則，把 e 加進 M；由於 M 是樹，這會恰好產生一個環。該環必須進出切割的 兩邊，所以環上還有另一條跨越邊 f。切割尊重 F，故 f 不屬於 F。因為 e 是最輕跨越邊，所以 w(e) ≤ w(f)。現在以 e 取代 f，所得圖仍是生成樹， 仍包含 F，而總權重沒有增加。原來的 M 已經最小，所以替換後仍是 MST。這個交換 論證說明貪心選擇可以延伸成全局最優解。

對 Prim 而言，每條獲接受的邊恰有一端在目前樹內，因此它跨越相應切割，而且不會成環。 對 Kruskal 而言，若候選邊 (u,v) 的兩端屬於不同森林分量，就考慮包圍 u 所在 分量的切割。按非遞減權重處理邊，使這條候選邊成為仍然有關的最輕跨越邊，交換論證 因而適用。

例題詳解

例題

MST 並不是最短路徑樹

考慮三角形：s-a 權重為 2，s-b 權重為 2，a-b 權重為 1。 一棵 MST 會選 a-b，再在 s-a 和 s-b 中選一條，總權重是 3。

但若源點是 s，最短路徑樹必須同時使用兩條權重為 2 的邊。由 s 直接到 a 或 b 的距離都是 2，繞經另一個非源點頂點則要 3。這棵最短路徑樹的 樹邊權重和是 4。它解決源點距離問題；MST 解決整個網絡的總連接成本問題。

Prim 演算法

Prim 維持已進入樹的頂點集合 S，每次接受恰有一端在 S 內的最輕邊。Tutorial 9 採用邊的優先佇列，因此以下版本與課件的狀態完全相配：

PRIM_WITH_EDGE_QUEUE(G, start):
    inTree[v] ← false，對每個頂點 v
    T ← 空邊集合
    pq ← 儲存 (weight, from, to) 的最小優先佇列

    inTree[start] ← true
    把所有 (start, x) 而且 x 尚未 inTree 的邊加入 pq

    當 pq 非空而且 |T| ≠ |V| - 1：
        (weight, u, v) ← pq.popMin()
        若 inTree[v]：
            跳過                 // 過期邊；兩端都在 S 內
        否則把 (u, v) 加入 T
        inTree[v] ← true
        對每條邊 (v, x)：
            若 x 尚未 inTree，就把 (weight(v,x), v, x) 加入 pq

    若 |T| ≠ |V| - 1，報告「圖不連通」；否則回傳 T

例題

Tutorial 9 的完整 Prim 追蹤

課件圖的頂點是 A,B,C,D,E，加權邊為

AB=1, BD=2, BC=3, AD=5, DE=6, DC=7, CE=8。

由 A 開始。下表同時記錄已接受的樹邊和優先佇列中的關鍵動作。

步驟	目前頂點集合 S	佇列動作與決定	已接受邊
0	{A}	放入 AB(1), AD(5)	無
1	{A,B}	取出 AB(1)；放入 BD(2), BC(3)	AB
2	{A,B,D}	取出 BD(2)；放入 DE(6), DC(7)	AB, BD
3	{A,B,C,D}	取出 BC(3)；放入 CE(8)	AB, BD, BC
4a	不變	取出 AD(5) 並拒絕：兩端已在 S 內	不變
4b	五個頂點全在內	取出並接受 DE(6)	AB, BD, BC, DE

所得樹有四條邊，符合五個頂點的要求，總權重為 1+2+3+6=12。拒絕 AD 並非 可有可無的佇列整理，而是邊優先佇列版本的防環步驟；若接受 AD，就會封閉 A-B-D-A 這個環。

用鄰接表時，每條邊會在其中一端加入樹時被檢查，推入及取出的佇列項目總數至多是 O(E)。二元 heap 最多保存 O(E) 個項目，所以時間為 O(E log E)，空間為 O(V+E)。對簡單圖，log E=O(log V)，故也常寫成 O(E log V)。這個分析專屬 上述邊佇列版本；若改用鄰接矩陣並在每輪掃描所有頂點，時間會是 O(V^2)。

Kruskal 演算法

Kruskal 不需要起點。起初每個頂點各自成為一個分量；演算法把所有邊按權重非遞減排序， 只有在候選邊兩端目前分屬不同分量時才接受它。

以下課程層次的實作在目前森林中搜尋，藉此判斷兩端是否已連通；它不假設任何額外的 分量資料結構。

KRUSKAL_WITH_FOREST_SEARCH(G):
    edges ← 所有邊，按權重非遞減排序
    F ← 包含全部頂點但沒有邊的圖
    若 F 已有 |V| - 1 條邊，就回傳 F    // 處理單頂點圖

    依次處理 edges 中的 (u, v)：
        若 HAS_PATH_BY_DFS_OR_BFS(F, u, v)：
            跳過                 // 加入 (u,v) 會形成環
        否則把 (u, v) 加入 F
        若 F 已有 |V| - 1 條邊，就回傳 F

    報告「圖不連通」

例題

同一來源圖的完整 Kruskal 追蹤

排序結果是

AB(1), BD(2), BC(3), AD(5), DE(6), DC(7), CE(8)。

候選邊	決定前兩端狀態	決定	決定後森林
AB(1)	A、B 分離	接受	{AB}
BD(2)	B、D 分離	接受	{AB,BD}
BC(3)	B、C 分離	接受	{AB,BD,BC}
AD(5)	已有路徑 A-B-D	拒絕：否則形成 A-B-D-A	不變
DE(6)	E 與其餘分量分離	接受並停止	{AB,BD,BC,DE}

總權重同樣是 12。接受四條邊後便毋須再處理 DC(7) 和 CE(8)。在這個例子中， 邊權重令有用選擇的先後次序沒有歧義，因此 Prim 和 Kruskal 得到同一棵樹；有權重 相同的邊時，兩者可能得到形狀不同但總權重相同的 MST。

排序成本是 O(E log E)。在這裏描述的實作中，已接受邊永遠形成森林，邊數少於 V；因此，在該森林做一次 DFS 或 BFS 最壞需要 O(V)，而每條候選邊都可能觸發 一次搜尋。總時間是 O(E log E + EV)，空間是 O(V+E)，當中包括排序邊表和 森林。若只報 O(E log E)，就漏算了文中明確執行的遍歷式成環測試，並不符合實作。

常見錯誤

常見錯誤

Prim 直接取全圖尚餘的最輕邊

Prim 只能選取由目前樹跨到外面頂點的邊。連接兩個外部頂點的便宜邊不會延伸目前樹； 連接兩個內部頂點的邊已過期，接受它會成環。

常見錯誤

Kruskal 見過所有頂點便停止

多個互不連通的分量加起來也可以提及全部頂點。只有接受 |V|-1 條邊後才可停止；對 連通輸入而言，此時森林才合成一棵生成樹。

常見錯誤

把 MST 路徑當成最短路徑

MST 只最小化一個全局總和，不保證其中指定兩點之間、或由指定源點出發的路徑，是原圖 中成本最低的路徑。

常見錯誤

以為 MST 要求權重非負

非負限制屬於 Dijkstra 的貪心確定論證，而不是 MST。即使有負權邊，Prim 和 Kruskal 仍然成立；切割與交換論證只比較權重大小，從未假設權重非負。

總結

• 無向圖連通時才有生成樹；生成樹包含全部頂點和恰好 |V|-1 條邊。
• MST 最小化所選邊的總權重，並不是最短路徑樹。
• Prim 以跨越目前切割的最輕邊，逐步擴展一棵連通樹。
• Kruskal 按權重次序擴展森林，若候選邊兩端已連通便拒絕它。
• 最輕跨越邊的交換論證說明兩種貪心選擇為何安全；顯式成環檢查則維持樹結構。
• 複雜度必須配合表示法和資料結構：文中的 Prim 邊佇列是 O(E log E)；Kruskal 若以遍歷檢查成環，則是 O(E log E + EV)。

練習

思考檢查

檢查 1：一張連通圖有 9 個頂點。它的任何生成樹必有多少條邊？為何不能更多？

同時使用「樹」的兩項條件：連通和無環。

思考檢查

檢查 2：在 Tutorial 9 圖中，Prim 已接受 AB、BD 和 BC。接着會檢查哪條佇列邊、如何處理，再接受哪條邊？

檢查候選邊的兩端是否都已在目前樹中。

思考檢查

檢查 3：為何只寫 O(E log E)，不足以描述本節用遍歷測試成環的 Kruskal 實作？

除了排序，還要計算每一次 HAS_PATH 的成本。

1. 在 Tutorial 9 圖中刪去 BD(2)，對其餘六條邊執行 Kruskal。記錄每次接受或 拒絕，並計算最後總權重。
2. 證明 Kruskal 使用的成環準則：把 (u,v) 加入森林會形成環，當且僅當森林內 原本已有一條由 u 到 v 的路徑。
3. 構造一張有兩棵不同 MST 的連通加權圖，並指出哪個權重相同情況容許兩個答案。
4. 解釋為何 Prim 在不連通圖上必須報告失敗，即使優先佇列實作完全正確。

答案與解答

解答 · 檢查 1 解答

必有 9-1=8 條邊。連接九個頂點至少需要八條邊，而樹恰好達到這個下限。若再加入 第九條邊，它會連接兩個在樹內已有唯一路徑的頂點，因而形成環。

解答 · 檢查 2 解答

佇列下一項是 AD(5)。A 和 D 都已在樹內，所以這項已過期，必須拒絕；否則會 形成 A-B-D-A。然後 Prim 接受 DE(6)，把 E 加進樹，完成四邊 MST。

解答 · 檢查 3 解答

排序是 O(E log E)，但每個候選都可能在有 V 個頂點、少於 V 條邊的森林中 觸發一次 DFS 或 BFS。一次搜尋是 O(V)，最多做 E 次，另加 O(EV)。因此配合 本文實作的界是 O(E log E + EV)。

解答 · 較長練習的引導解答

1. 新次序是 AB(1), BC(3), AD(5), DE(6), DC(7), CE(8)。依次接受 AB、 BC、AD、DE；此時四條邊已連接五個頂點，總權重是 1+3+5+6=15，在停止 以前沒有候選被拒絕。
2. 若原本已有由 u 到 v 的路徑，該路徑連同 (u,v) 就是一個環。反過來，若 新增 (u,v) 後產生環，從該環刪去新邊，餘下部分就是原森林中的 u 至 v 路徑，故兩個條件等價。
3. 三角形三條邊的權重都設為 1 即可。任何兩條邊都形成總權重為 2 的生成樹， 因而共有三棵 MST。安全的最輕邊在權重相同時未必唯一。
4. Prim 只能到達起點所在的連通分量。最後優先佇列會變空，但已接受邊仍少於 |V|-1。由已到達分量跨向其他頂點的邊不存在，這正好證明整張圖沒有生成樹。