最小生成樹：用最少的錢連起所有村莊

一個經典問題

N 個村莊要互相連網路，任兩個村莊之間至少要連得通（不一定直連）。每條線路有建設費用。問：最少花多少錢能讓所有村莊互通？

這就是最小生成樹 (Minimum Spanning Tree, MST) 問題：

生成樹：包含所有 V 個點、用 V-1 條邊、無環
最小：邊權重總和最小

兩種解法

Kruskal：從小邊開始貪婪

「把所有邊按權重排序，從最小的開始挑，挑了會形成環就跳過」——這就是 Kruskal。

判斷會不會形成環？用 Union-Find！（第 21 章）

跑一遍：村莊 A, B, C, D, E，邊：

A-B: 4, A-C: 1, B-C: 3, B-D: 5, C-D: 2, C-E: 7, D-E: 6

按權重排序：A-C(1), C-D(2), B-C(3), A-B(4), B-D(5), D-E(6), C-E(7)

邊	權重	加？	原因
A-C	1	✓	不會成環
C-D	2	✓	不會成環
B-C	3	✓	不會成環
A-B	4	✗	A 和 B 已經連通（成環）
B-D	5	✗	B 和 D 已經連通
D-E	6	✓	把 E 接進來
C-E	7	—	已經 V-1=4 條邊，停

MST 總權重 = 1 + 2 + 3 + 6 = 12。

Pseudocode（Kruskal）

Algorithm Kruskal(graph):

edges ← 所有邊按權重排序

uf ← UnionFind(V)

mst ← []

for (u, v, w) in edges:

if uf.find(u) ≠ uf.find(v):

mst.append((u, v))

uf.union(u, v)

if len(mst) == V-1: break

return mst

時間：排序 O(E log E) + V 次 union-find O(E × α(V)) = O(E log E)。

Prim：從一個點長出來

從任一點開始，每次找「已知點集合連到外界的最便宜邊」加進來——像滾雪球。

跑同一張圖，從 A 開始：

步驟	已知點集合	加入哪條邊	為什麼
1	{A}	A-C (1)	唯一連 A 的最便宜外邊
2	{A, C}	C-D (2)	C 到外的最便宜
3	{A, C, D}	B-C (3)	已知集合到外的最便宜
4	{A, B, C, D}	D-E (6)	接 E
5	{A, B, C, D, E}	—	完成

MST 一樣 = 1 + 2 + 3 + 6 = 12。

Pseudocode（Prim, 用 Priority Queue）

Algorithm Prim(graph, start):

visited ← {start}

pq ← PriorityQueue() // 按 weight

for (start, v, w) in graph[start]: pq.push((w, start, v))

mst ← []

while pq not empty and len(mst) < V-1:

(w, u, v) ← pq.pop()

if v in visited: continue

visited.add(v); mst.append((u, v))

for (v, x, w2) in graph[v]:

if x not in visited: pq.push((w2, v, x))

return mst

時間：用 binary heap O(E log V)。

Kruskal vs Prim

	Kruskal	Prim
想法	從小邊開始挑（全域貪婪）	從一點滾雪球（局部擴張）
資料結構	Union-Find	Priority Queue
時間	O(E log E)	O(E log V)
適合	稀疏圖（E 小）	稠密圖（E 大）

兩個結果都是 MST，但實際選的邊可能不同（如果有相等權重的邊）。

💡MST 為什麼能用貪婪？

Cut Property（割邊性質）：把圖分成兩半，兩半之間最便宜的那條邊一定在某個 MST 裡。

Kruskal 和 Prim 都基於這個性質——所以每次的貪婪選擇都是安全的。（嚴格證明在演算法導論 23 章，考試不太會考證明本身。）

為什麼是「樹」？

V 個點要互通最少需要 V-1 條邊。多於 V-1 條 → 必有環（環裡有可刪的邊 → 不是最小）。

所以 MST 一定是樹（無環的連通圖）。

📝考試會這樣考

題型一：跑一遍 Kruskal。 給帶權圖，列出每步：

當前處理的邊
加入或跳過（原因）
Union-Find 狀態

題型二：跑一遍 Prim（從某點開始）。 列出每步：

已知點集合
Priority Queue 內容
加入哪條邊

題型三：Kruskal vs Prim 適用場景。

邊很少（稀疏）→ Kruskal（排序便宜）
邊很多（稠密）→ Prim（不用一次處理所有邊）

題型四：MST 唯一嗎？ 答：邊權都不同 → 唯一。有相等權重 → 可能有多個 MST，但總權重都一樣。

題型五：證明 Kruskal 是對的（簡答）。 答：基於 Cut Property——目前處理的最便宜邊跨越「已成樹」和「未加入點」，這條邊一定在某個 MST 裡。

這章記住

MST = V 個點 + V-1 條邊 + 權重和最小。
Kruskal：邊排序 + Union-Find，O(E log E)，稀疏圖用。
Prim：Priority Queue 滾雪球，O(E log V)，稠密圖用。
兩個都是貪婪演算法，基於 Cut Property 保證正確。
結果權重一定相同，邊可能不同（同權重時）。