# 最小生成樹 Minimum Spanning Tree
在一些路網的構建當中，我們時常期望可以找出一個最簡的路網，使資料可以互相傳遞，而且花費最小。要實現這樣的想法，就會用到最小生成樹的概念

## 生成樹 Spanning Tree
### 定義
若一棵樹 $T$ 是一張連通圖 $G$ 的子圖，且 $V(T) = V(G)$ (即 $T$ 擁有所有 $G$ 的節點)，則稱 $T$ 為一棵生成樹

<center class = "center">
<img src="https://hackmd.io/_uploads/B1NKHX98kl.png" style="width: 340px">
<img src="https://hackmd.io/_uploads/Hy6qrXcLJg.png" style="width: 350px">
</center>

<p class="text-center">
下圖就是上圖的生成樹
</p>

### 性質
因為生成樹 $T$ 是一棵樹，必須符合樹的性質:
1. $|E| = |V| - 1$
2. 無環
3. 為一張連通圖
4. 任兩節點 $u, v\in V(T)$ 只會有一條唯一的路徑 $p$

由於一張圖會有多個子圖，而 $T$ 也是連通圖 $G$ 的子圖，因此 $T$ 可能會有很多種

## 常見的生成樹例子
### 深度優先搜尋樹 DFS Tree
[深度優先搜尋 (DFS)](https://hackmd.io/@ShanC/bfs_dfs) 會訪問圖上的所有節點。事實上將走訪路徑保留後，可以連接所有節點形成一顆生成樹

### 廣度優先搜尋樹 BFS Tree
相同地，BFS 也後產生一顆生成樹。此生成樹會有一個性質 : 根節點所有其他點的距離為最短

## 最小生成樹 Minimum Spanning Tree
通常 Minimum Spanning Tree 會簡寫成 MST
### 樹的權重
一棵樹的權重，就是所有邊權重的和
設一棵樹 $T = (V, E)$，則用數學式可表達成 : $\sum_{v\in V} w(v)$

### 定義
最小生樹就是所有生成樹當中樹的權重最小的那一棵
根據生成樹的性質，最小生成樹也可能有多種可能

<center class = "half">
<img src="https://hackmd.io/_uploads/SJ79LQ98yl.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/HJmiUX98Je.png" style="width: 350px">
</center>

<p class="text-center">
右圖就是左圖的最小生成樹
</p>

## Prim 演算法
### 想法
Prim 演算法是一個尋找 MST 的貪心演算法。核心概念是想維護一個集合 $S$，使 $S$ 最終包含連通圖中所有節點

設一張連通圖 $G=(V, E)$
1. 在最開始找個起點 $t\in V$ 裝入 $S$ 中
2. 重複將連接集合 $S$ 與 $V-S$ 的邊中最小權重的那一條所連接的節點 $v\in V-S$ 併入 $S$，直到 $S = V$ 時就停止

### 實作程式碼 (原始版)
- $\text{g[ ]}$ : 鄰接陣列
- $\text{vis[ i ]}$ : 紀錄節點 $\text{i}$ 是否在集合 $S$ 中
- $\text{key[ i ]}$ : 暫存與節點 $\text{i}$ 所聯的邊權
- $\text{f[ i ]}$ : 紀錄每個節點 $\text{i}$ 的父親是誰
- $\text{n}$ : 節點的數量
- $\text{m}$ : 邊的數量

typedef pair<int, int> pii;
vector<pii> g[MAXN];  // 儲存鄰接陣列: g[u] = {v, w}
int n, m; // 節點數、邊數

int prim(int start){ // 0-based
    vector<bool> vis(n, false); 
    vector<int> key(n, INT_MAX);
    vector<int> f(n);
    
    f[start] = -1; // 起點沒有父親
    key[start] = 0;
    
    for(int i = 0; i < n - 1; i++){ // 最多只會走 n - 1 條邊
        int mn = INT_MAX, idx = 0;
        for(int j = 0; j < n; j++){
            if(!vis[j] && mn > key[j])
                mn = key[j], idx = j;
        }
        
        vis[idx] = true;
            
        int u = idx;
        for(pii j : g[u]){ // 找所有與 u 相鄰的節點
            int v = j.first, w = j.second;
            if(!vis[v] && w < key[v]){
                f[v] = u;
                key[v] = w;
            }
        }
    }
    
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += key[i];
    return ans;
}

### 實作程式碼 (以 priority queue 優化)
由於整個算法使用 priority queue 寫，感覺會很像 BFS
- $\text{g[ ]}$ : 鄰接陣列
- $\text{vis[ i ]}$ : 紀錄節點 $\text{i}$ 是否在集合 $S$ 中
- $\text{n}$ : 節點的數量
- $\text{m}$ : 邊的數量

typedef pair<int, int> pii;
int n, m; // 節點數、邊數
vector<pii> g[MAXN]; // 儲存鄰接陣列: g[u] = {v, w}

int prim(int start){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start}); // 將開始的節點放入 pq
    vector<bool> vis(m, false);
    int ans = 0;
    
    while(!pq.empty()){
        int u = pq.top().second;
        int w = pq.top().first;
        pq.pop();
        
        if(vis[u])
            continue;
        vis[u] = true;
        ans += w;
        
        for(pii i : g[u]){
            int v = i.first, w = i.second;
            if(!vis[v])
                pq.push({w, v});
            // 因為是以權重優先，所以反著放入 pq
        }
    }
    
    return ans;
}

### 時間複雜度
#### 原始版
總時間複雜度: $O(n^2)$，因為雙重迴圈

#### priority queue 優化版
- $\text{pq.push()}$ : $O(log~m)$
- $\text{pq.pop()}$ : $O(log~m)$
- 遍歷所有節點 (很像 BFS): $O(n + m)=O(m)$，因為邊數通常比較多，所以取個上限

總時間複雜度: $O(m~log~m)$

### 缺點
挑選不同的起點會影響整個演算法的運作

## Kruskal 演算法
### 想法
Kruskal 演算法是一個尋找 MST 的貪心演算法。核心概念是把邊依照權重由小排到大，再使用[併查集](https://hackmd.io/@ShanC/dsu)維護集合，使其中一個集合最終包含連通圖中所有節點

設一張連通圖 $G=(V, E)$
1. 設 $i = 1$
2. 檢查第 $i$ 小的邊兩終點是否在同一個集合
3. 如果不是在同一個集合就將兩集合取聯集
4. $i$++，回到 1. 直到將所有邊都遍歷

sort E with the weight in ascending order
w = 0 # the weight of the spanning tree 
for each e in E:
    if e.u and e.v are not in the same set:
        union the set of e.u and the set of e.v
        w += e.weight

### 實作程式碼
併查集因為之前提過，為了版面大小，這裡就省略實作細節

int n, m; // 節點數、邊數
struct Edge{
    int u, v, w;
    bool operator<(const Edge a){ // 定義運算子
        return w < a.w; // 排序時依照邊權由小排到大
    }
};
vector<Edge> edges; // 用 vector 存邊

int kruskal(){
    int ans = 0; // 紀錄答案
    dsu.init(n); // 將併查集初始化
    
    sort(edges.begin(), edges.end()); // 排序
    for(int i = 0; i < m; i++){
        Edge e = edges[i];
        if(dsu.find(e.u) != dsu.find(e.v)){ // 兩終點在不同集合
            ans += e.w; // 更新答案
            dsu.merge(e.u, e.v); // 取聯集
            if(dsu.sz[dsu.find(e.u)] == n)
                break; // 如果確定全部節點都找完了，就離開迴圈
        }
    }
    
    return ans;
}

### 時間複雜度
- 併查集初始化: $O(n)$
- 查詢所在集合: $O(\alpha(n))\approx O(1)$
- 合併: $O(\alpha(n)) \times 2 + O(1)\approx O(1)$
- 排序所有邊: $O(m~log~m)$

總時間複雜度: $O(m~log~m)$
由於邊數最多 $\cfrac{n(n - 1)}{2}$ 條，因此總時間複雜度也可以改寫成:
$O(m~log~n^2)=O(2m~log~n)=O(m~log~n)$

## 證明 Prim 演算法與 Kruskal 演算法的正確性
講到這裡，不知有沒有人好奇為什麼這兩種演算法是正確的，難道就不會產生不是生成樹的結果嗎? 接下來要來證明這兩種演算法為什麼是對的

### 尋找 MST 的通用演算法
首先必須來將 Prim 演算法與 Kruskal 演算法一般化:
先定義 $A$ 是某個最小生成樹的子集合

find-a-MST(G):
    A := ∅
    while A does not form a spanning tree:
        find an edge (u, v) that is safe for A
        A := A ∪ {(u, v)}
    return A

以上這段程式每一步都會找出一條邊 $(u, v)$，使 $A \cup \{(u, v)\}$ 也是某棵 MST 的子集合。我們可以將這種不違反「$A$ 是某個最小生成樹的子集合」性質的邊 $(u, v)$ 稱為安全邊

### 名詞定義
對於一無向圖 $G=(V, E)$
- 割線 (cut): $V$ 做分割，以 $(S, V - S)$ 來表示
- 跨越 (cross): 如果一條邊的兩終點分別在 $S$ 與 $V - S$ 之間，就說那條邊跨越割線 $(S, V - S)$
- 尊重 (respect): 如果 $A$ 沒有跨越割線的邊，則稱割線尊重 $A$
- 輕邊 (light edge): 跨越割線的邊之中，最輕的那一條稱為輕邊

### 定理: 安全性

#### 敘述
設 $G=(V, E)$ 是連通的無向圖，且有一個權重函數 $w: E \to \mathbb{R}$。設 $A$ 是 $E$ 的子集合，且 $A$ 屬於 $G$ 的某個 MST。設 $(S, V - S)$ 是在 $G$ 中尊重 $A$ 的任何一條割線，且 (u, v) 是跨越 $(S, V - S)$ 的輕邊，則$(u, v)$ 對 $A$ 來說是安全的

<center>
<img src="https://hackmd.io/_uploads/HJ4yN6c8yl.png" style="margin: 0 auto; display: block; width: 600px">
</center>

#### 證明
設 $T$ 是一個包含 $A$ 的 MST，則可能會有以下狀況:
- Case1 : 如果 $(u, v)\in T$，則這個東西沒問題
- Case2 : $(u, v)\notin T$，則需要找到另一棵 MST $T'$，使 $A\cup\{(u, v)\} \subseteq T'$

以下說明 $T'$ 是一棵 MST:
因為 $T$ 是一棵 MST，必存在 $u,v$-路徑 $p$，使路徑上至少有一條邊跨越 $(S, V-S)$。設 $(x, y)\in p$ 為任一條這種跨越 $(S, V-S)$ 的邊。因為割線尊重 $A$，所以 $(x, y)$ 不在 $A$ 裡面。將 $(x, y)$ 移除，再將 $(u, v)$ 接回去會產生一顆新的 MST $T'$。總結來說就是以下
- $T'=T - \{(x, y)\}~\cup~\{(u, v)\}$，這說明 $T$ 是一棵生成樹

接下來，又因為 $(u,v)$ 是一條跨越 $(S, V-S)$ 的輕邊，因此 $w(u, v) \leq w(x, y)$，可推得以下結論
- $w(T')=w(T) - w(x, y) + w(u, v)\leq w(T)$，選擇 $(u,v)$ 之後的樹權會比選 $(x, y)$ 的樹權來的小

最後需要證明 $(u, v)$ 是安全邊:
因為 $A\subseteq T$ 且 $(x, y)\notin A$，所以 $A\subseteq T-\{(x, y)\}\subseteq T'$。因為 $T'$ 是 MST，所以 $(u, v)$ 是安全的

由以上證明，可以說明演算法是正確的

## 題目練習

[CSES Road Reparation](https://cses.fi/problemset/task/1675) (裸題)
[Zerojudge a129. 最小生成樹](https://zerojudge.tw/ShowProblem?problemid=a129) (裸題)
[Zerojudge e509. Conscription](https://zerojudge.tw/ShowProblem?problemid=e509) (最大生成樹??)
[Zerojudge f506. 11747 - Heavy Cycle Edges](https://zerojudge.tw/ShowProblem?problemid=f506)
[AtCoder ABC_235 E - MST + 1](https://atcoder.jp/contests/abc235/tasks/abc235_e?lang=en) (改一下原本的演算法，動動腦)
[AtCoder ABC_065 D - Built?](https://atcoder.jp/contests/abc065/tasks/arc076_b) (因為貪心的緣故，基本上只需要連最近的 x 座標距離及最近的 y 座標距離)
[Zerojudge c495. 四、次小生成樹(SBMST)](https://zerojudge.tw/ShowProblem?problemid=c495) (需要用到最低共同祖先的原理)
[Zerojudge k715. 糧食便道 (Supply)](https://zerojudge.tw/ShowProblem?problemid=k715)
[Zerojudge q839. 4. 分組遊戲](https://zerojudge.tw/ShowProblem?problemid=q839) (Kruskal 到第 $k-1$ 小的邊)

----

## 參考資料
- Introduction to Algorithms, Fourth Edition
- [spanning tree - 台師大演算法筆記](https://web.ntnu.edu.tw/~algo/SpanningTree.html)
- [geeksforgeeks Prim’s Algorithm for Minimum Spanning Tree (MST)](https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/)
- [Graph Theory & DSU - 海大競程](https://hackmd.io/@LeeShoWhaodian/2024I2CP_DSUandGraph#/3)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/1/7