最小生成樹 Minimum Spanning Tree

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

生成樹 Spanning Tree

定義

若一棵樹

$T$ 是一張連通圖

$G$ 的子圖，且

$V(T)=V(G)$ (即

$T$ 擁有所有

$G$ 的節點)，則稱

$T$ 為一棵生成樹

下圖就是上圖的生成樹

性質

因為生成樹

$T$ 是一棵樹，必須符合樹的性質:

1. $|E|=|V|-1$
2. 無環
3. 為一張連通圖
4. 任兩節點
   $u,v\in V(T)$ 只會有一條唯一的路徑
   $p$

由於一張圖會有多個子圖，而

$T$ 也是連通圖

$G$ 的子圖，因此

$T$ 可能會有很多種

常見的生成樹例子

深度優先搜尋樹 DFS Tree

深度優先搜尋 (DFS) 會訪問圖上的所有節點。事實上將走訪路徑保留後，可以連接所有節點形成一顆生成樹

廣度優先搜尋樹 BFS Tree

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

最小生成樹 Minimum Spanning Tree

通常 Minimum Spanning Tree 會簡寫成 MST

樹的權重

一棵樹的權重，就是所有邊權重的和
設一棵樹

$T=(V,E)$，則用數學式可表達成 :

$\sum _{v\in V}w(v)$

定義

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

右圖就是左圖的最小生成樹

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(logm)$
• $\text{pq.pop()}$ :
  $O(logm)$
• 遍歷所有節點 (很像 BFS):
  $O(n+m)=O(m)$，因為邊數通常比較多，所以取個上限

總時間複雜度:

$O(mlogm)$

缺點

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

Kruskal 演算法

想法

Kruskal 演算法是一個尋找 MST 的貪心演算法。核心概念是把邊依照權重由小排到大，再使用併查集維護集合，使其中一個集合最終包含連通圖中所有節點

設一張連通圖

$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(mlogm)$

總時間複雜度:

$O(mlogm)$
由於邊數最多

$\frac{n(n-1)}{2}$ 條，因此總時間複雜度也可以改寫成:

$O(mlog{n}^2)=O(2mlogn)=O(mlogn)$

證明 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$ 來說是安全的

證明

設

$T$ 是一個包含

$A$ 的 MST，則可能會有以下狀況:

• Case1 : 如果
  $(u,v)\in T$，則這個東西沒問題
• Case2 :
  $(u,v)\notin T$，則需要找到另一棵 MST
  $T^{\prime }$，使
  $A\cup \{(u,v)\}\subseteq T^{\prime }$

以下說明

$T^{\prime }$ 是一棵 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^{\prime }$。總結來說就是以下

• $T^{\prime }=T-\{(x,y)\}\cup \{(u,v)\}$，這說明
  $T$ 是一棵生成樹

接下來，又因為

$(u,v)$ 是一條跨越

$(S,V-S)$ 的輕邊，因此

$w(u,v)\le w(x,y)$，可推得以下結論

• $w(T^{\prime })=w(T)-w(x,y)+w(u,v)\le w(T)$，選擇
  $(u,v)$ 之後的樹權會比選
  $(x,y)$ 的樹權來的小

最後需要證明

$(u,v)$ 是安全邊:
因為

$A\subseteq T$ 且

$(x,y)\notin A$，所以

$A\subseteq T-\{(x,y)\}\subseteq T^{\prime }$。因為

$T^{\prime }$ 是 MST，所以

$(u,v)$ 是安全的

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

題目練習

CSES Road Reparation (裸題)
Zerojudge a129. 最小生成樹 (裸題)
Zerojudge e509. Conscription (最大生成樹??)
Zerojudge f506. 11747 - Heavy Cycle Edges
AtCoder ABC_235 E - MST + 1 (改一下原本的演算法，動動腦)
AtCoder ABC_065 D - Built? (因為貪心的緣故，基本上只需要連最近的 x 座標距離及最近的 y 座標距離)
Zerojudge c495. 四、次小生成樹(SBMST) (需要用到最低共同祖先的原理)
Zerojudge k715. 糧食便道 (Supply)

---

參考資料

• Introduction to Algorithms, Fourth Edition
• spanning tree - 台師大演算法筆記
• geeksforgeeks Prim’s Algorithm for Minimum Spanning Tree (MST)
• Graph Theory & DSU - 海大競程

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/1/7