第三部分：路徑規劃（續）¶

< 上一題：最短路徑計算 | 返回目錄 | 下一題：頻寬容量分析 >

場景：用最少成本建立備援網路¶

主管說：「我們需要**備援光纖**，確保任何一條主線路斷掉，資料中心之間還能連通。」

你看了報價單：每條光纖的建設成本從 $50K 到 $500K 不等。

「怎麼用最少的錢，讓所有資料中心都連通？」

這就是**最小生成樹（Minimum Spanning Tree, MST）** 問題。

第 6 題：備援網路建設 - MST (Kruskal & Prim)¶

(a) MST 定義與性質¶

3 分 ・大二

你需要知道：什麼是生成樹？什麼是最小生成樹？

題目：

定義**生成樹（Spanning Tree）**
定義**最小生成樹（MST）**
說明 Cut Property（切割性質）：為什麼它是 MST 演算法正確性的基礎？

解答

1. 生成樹：

給定連通圖 $G = (V, E)$，生成樹是 $G$ 的一個子圖 $T = (V, E')$，滿足： - 包含所有頂點 $V$ - $T$ 是樹（連通且無環） - $|E'| = |V| - 1$

2. 最小生成樹：

在所有生成樹中，**邊權總和最小**的那一棵。

\[\text{MST} = \arg\min_{T} \sum_{e \in T} w(e)\]

3. Cut Property：

切割（Cut）：把頂點分成兩個非空集合 $S$ 和 $V-S$。

跨越邊（Crossing Edge）：一端在 $S$，一端在 $V-S$ 的邊。

Cut Property：對於任意切割，最小的跨越邊一定在某個 MST 中。

直覺：要連接 $S$ 和 $V-S$，必須選一條跨越邊。選最小的那條不會錯。

證明（反證）：假設最小跨越邊 $e$ 不在 MST $T$ 中。$T$ 必有另一條跨越邊 $e'$。把 $e$ 加入 $T$，形成環，移除 $e'$，得到權重更小的生成樹。矛盾！

(b) Kruskal 演算法¶

4 分 ・大三

你需要知道：如何用貪心策略建構 MST？

題目：

說明 Kruskal 演算法的步驟
什麼是 Union-Find（並查集）？它如何幫助 Kruskal？
分析時間複雜度

解答

1. Kruskal 步驟：

把所有邊按權重排序
初始化：每個頂點自成一個連通分量
依序考慮每條邊：
如果這條邊連接**不同的連通分量** → 加入 MST
如果連接**同一個連通分量** → 跳過（會形成環）
直到加入 $V-1$ 條邊

def kruskal(V, edges):
    edges.sort(key=lambda x: x[2])  # 按權重排序
    uf = UnionFind(V)
    mst = []

    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            mst.append((u, v, w))
            uf.union(u, v)
            if len(mst) == V - 1:
                break

    return mst

2. Union-Find：

功能： - find(x)：找 $x$ 所屬的集合（代表元素） - union(x, y)：合併 $x$ 和 $y$ 所在的集合

實現（Path Compression + Union by Rank）：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

3. 時間複雜度：

排序：$O(E \log E)$
$E$ 次 find/union：$O(E \cdot \alpha(V))$（$\alpha$ 是反 Ackermann 函數，實際上是常數）

總時間：$O(E \log E) = O(E \log V)$（因為 $E \leq V^2$）

© Prim 演算法¶

4 分 ・大三

你需要知道：另一種建構 MST 的方式

題目：

說明 Prim 演算法的步驟
用 Priority Queue 實現 Prim
比較 Kruskal 和 Prim 的適用場景

解答

1. Prim 步驟：

從任意頂點 $s$ 開始，$S = \{s\}$
重複：
找**從 $S$ 出發、到達 $V-S$** 的最小邊 $(u, v)$
把 $v$ 加入 $S$，把 $(u, v)$ 加入 MST
直到 $S = V$

像 Dijkstra 的「成長過程」，不斷把 MST 擴大一個頂點。

2. 實現：

import heapq

def prim(graph, start):
    V = len(graph)
    in_mst = [False] * V
    mst = []
    pq = [(0, start, -1)]  # (權重, 頂點, 來自)

    while pq and len(mst) < V - 1:
        w, u, parent = heapq.heappop(pq)
        if in_mst[u]:
            continue
        in_mst[u] = True
        if parent != -1:
            mst.append((parent, u, w))

        for v, weight in graph[u]:
            if not in_mst[v]:
                heapq.heappush(pq, (weight, v, u))

    return mst

3. Kruskal vs Prim：

	Kruskal	Prim
策略	邊導向（全局排序）	頂點導向（局部擴展）
時間	$O(E \log E)$	$O(E \log V)$（Binary Heap）
		$O(E + V \log V)$（Fibonacci Heap）
適合	稀疏圖、邊已排序	稠密圖、需要 decrease-key

(d) MST 唯一性¶

4 分 ・碩一

你需要知道：MST 什麼時候是唯一的？

題目：

舉例說明 MST 可能**不唯一**
證明：如果所有邊權重都**不同**，則 MST 唯一

解答

1. 不唯一的例子：

A --1-- B
|       |
1       1
|       |
C --1-- D

所有邊權重都是 1。MST 需要 3 條邊，有多種選法。

2. 唯一性證明：

假設有兩個不同的 MST：$T_1$ 和 $T_2$。

設 $e$ 是「在 $T_1$ 但不在 $T_2$」的**最小權邊**。

把 $e$ 加入 $T_2$ 會形成環 $C$。$C$ 中必有一條邊 $e'$ 在 $T_2$ 但不在 $T_1$。

由於 $e$ 是最小的「差異邊」，$w(e) < w(e')$（邊權都不同）。

把 $T_2$ 中的 $e'$ 換成 $e$，得到更小的生成樹。矛盾！

所以 MST 唯一。

進階挑戰：判斷某邊是否在所有 MST 中¶

3 分 ・碩一

你需要知道：某條特定的邊，是否一定會被選入 MST？

題目：

給定圖 $G$ 和某條邊 $e = (u, v, w)$，設計演算法判斷：$e$ 是否出現在**所有** MST 中？

解答

方法：

暫時移除邊 $e$
只考慮權重 $< w$ 的邊，用這些邊做 Union-Find
檢查 $u$ 和 $v$ 是否已經連通

如果已經連通：存在不經過 $e$ 的替代路徑，$e$ 不是必須的

如果不連通：$e$ 是連接 $u$ 所在分量和 $v$ 所在分量的**最小邊**（或之一），必在某些 MST 中

進一步判斷是否在「所有」MST 中：

$e$ 在所有 MST 中 $\Leftrightarrow$ $e$ 是某個切割的**唯一最小跨越邊**

如果存在同權重的平行替代邊，則 $e$ 不在所有 MST 中。

第 6 題小結：你的備援網路工具箱¶

「用最少成本讓所有資料中心連通」
    │
    ├─► (a) 問題定義？→ MST
    │       → 連通、無環、邊權和最小
    │       → Cut Property 是正確性基礎
    │
    ├─► (b) 邊導向建構？→ Kruskal
    │       → 排序 + Union-Find
    │       → O(E log E)
    │
    ├─► (c) 頂點導向建構？→ Prim
    │       → Priority Queue 擴展
    │       → O(E log V) 或更好
    │
    └─► (d) MST 唯一嗎？
            → 邊權都不同 → 唯一
            → 有相同邊權 → 可能多個

演算法	策略	時間	適合
Kruskal	全局排序邊	$O(E \log E)$	稀疏圖
Prim	局部擴展頂點	$O(E \log V)$	稠密圖

< 上一題：最短路徑計算 | 返回目錄 | 下一題：頻寬容量分析 >

演算法	策略	時間	適合
Kruskal	全局排序邊	\(O(E \log E)\)	稀疏圖
Prim	局部擴展頂點	\(O(E \log V)\)	稠密圖