最小生成樹

我們直接來看一道問題：

從一張圖中，挑出一些點、一些邊，所構成的新圖就稱作原圖的一個子圖（subgraph）。這道題目翻譯成圖論的術語，就是「選出一個連通、有 $n$ 個節點，且邊權總和最小的子圖」。我們先思考一個簡單的版本：如果邊權都是 $1$，那目標就是挑出一個「邊數最少的連通子圖」。

先前樹的內容曾介紹過，圖論裡 $N$ 個點的樹（tree）是一張特別的無向圖：藉著恰 $N-1$ 條邊使所有點連通。樹上面不會有環，多一條邊就一定會造出一個環，少一條邊則會使圖不連通。不難發現，要讓 $N$ 個節點連通，當然是至少需要 $N-1$ 條邊，而一張 $N$ 個點、$N-1$ 條邊的連通圖，就是一棵樹了，因此要是可以在圖裡面找到一棵樹，它就很明顯是邊數最少的連通子圖！

一張 $N$ 點無向圖的生成樹（spanning tree），就是這張圖的其中一個子圖，這個子圖必須也是一棵 $N$ 個點的樹。換句話說，生成樹在做的事，就是從原本的邊集 $E$ 裡面，選出 $N-1$ 條邊，能和原本的所有點一起形成一棵樹。

以下這兩個子圖都是原圖的生成樹。

生成樹是圖論裡很重要的一個概念。想像我們要在這些節點上處理重要的資料，有很多條邊可以互相傳遞訊息；但維護每條邊的成本可能無法忽略，啟用太多連結也容易互相干擾、增加處理難度。這時生成樹就是一個可能的解方，因為它選出了最少的邊，連接著最多的節點，同時保有清楚明瞭的結構。

在眾多生成樹之中，有一些特別的生成樹，例如 DFS Tree、BFS Tree，和本文主題最小生成樹等。這些生成樹有特殊的性質，可以用來解決很多不簡單的問題，非常強大，未來還有不少戲份；但筆者想在此先幫各位施打預防針：別被這些概念嚇到了，它們只是比較厲害一點的生成樹而已！

進入正題，我們本來想要找的是「邊權總和最小」的連通子圖，我們要問的第一個問題是，答案會是一個生成樹嗎？在權重都是正數的時候沒錯，因為要是答案不是一棵樹，就代表答案的子圖上面有環，而在這個環上拔掉一條邊以後，整個環剩下的部分還是連起來的，因此圖仍然是連通的，並且因為權重是正數，權重總和會變小，我們就找到一個權重總和更小的連通子圖了。

所以說，我們的目標是找到最小生成樹（Minimum Spanning Tree，簡稱 MST），也就是能使總權重最小的生成樹。

在開始討論如何找一棵 MST 之前，我們先多談一些關於 MST 的事情。雖然剛才的例題中，保證權重都是正的，但實際上我們也可以在權重是任何實數的圖上定義 MST，一樣是使總權重最小的生成樹（不過要注意「權重最小的連通子圖」在有負邊的圖就是不同意思了），而且不同於最短路徑，在有負邊時會發生奇怪的事情，對最小生成樹來說，圖上有負邊完全沒差，作法一模一樣，以下介紹的所有作法和性質都可以直接套在有負邊的圖上。

另外，跟最小生成樹同理，也可以定義最大生成樹，就是權重總和最大的生成樹，縮寫也恰好是 MST；實際上，最大生成樹就是圖上每個邊權都乘上一個負號的最小生成樹，所以直接套用最小生成樹的作法就可以了，而大家慣例喜歡討論最小生成樹，所以聽到 MST 大概都有共識、不會弄錯。

一般而言，MST 不一定是唯一的。前面提到生成樹可能有很多種，任兩棵不同的生成樹有可能加總出一樣的值；而這個值也當然可能剛好是能達到的最小值，那樣的話這兩棵樹就都會是 MST。

我們之後才會討論到 MST 唯一的充分、必要條件，所以總是預設可能有多個 MST。本文想先處理的是，這張圖的 MST 權重是多少？那就還不用管 MST 的唯一性，只需要找到一棵肯定是 MST 的生成樹，就能回答這個問題了。

不失一般性，我們假設所有邊權都相異。

這是一個很強的假設：怎麼可能 $M$ 條邊這麼剛好，都沒有重複的權重呢？它的意思其實是，我們可以先任意給相同的邊權一個 tie-breaker，假裝他們的邊權是不同的。如此一來，任兩條邊總是分得出誰大誰小，成功避免掉選擇障礙的窘境。畢竟我們只需要找到一棵 MST 嘛。

但這樣說不定無法指引我們到 MST 啊？搞不好別種 tie-breaker 會給出更小的生成樹，或甚至其實不能做任何 tie-break。

先假設我們有個演算法，可以在邊權全相異時找到一棵正確的 MST。事實上，任選 tie-breaker 就相當於找一個超級小的數字 $\varepsilon$，若有 $k$ 條邊的邊權都是 $w$ 就隨便把這些邊權變成相異的 $w+\varepsilon, w+2\varepsilon, \dots,w+k\varepsilon$。選定 tie-breaker 以後，若我們的 MST 演算法給出的生成樹權重是 $W+V\varepsilon$ 好了，那麼

• 真正的 MST 權重不會超過 $W$，因為我們找到的那棵生成樹原本就是 $W$。
• 若真正的 MST 權重比 $W$ 小，那在我們的 tie-breaker 下那棵樹的權重會比 $W+V\varepsilon$ 小，矛盾。

所以真正的 MST 權重就是 $W$！也就是只要會做邊權相異的情況，那剩下的只須任選 tie-breaker 就能用同樣方式處理了。

以下兩個重要性質的敘述，是基於所有邊權相異的假設。推廣到一般的情況並不難，留給讀者練習，也會在將來派上用場。

證明

以下使用反證法。假設存在某個環 $C$ 的最大邊 $e$，有在某一棵最小生成樹 $T$ 上。

把 $e$ 從 $T$ 移除的話，$T$ 被分為兩半；而 $C$ 上除了 $e$ 以外，一定有至少一條邊跨越了這兩半。

所以只要選一條邊 $e'$ 加回來，它又變成了一棵生成樹 $T'$。根據 $e$ 是 $C$ 上的最大邊權，$T'$ 的權重一定比 $T$ 還小，代表 $T$ 不是 MST，矛盾了！

證明

繼續使用反證法。假設某個 cut 上面最小的邊是 $e$，而且存在某個最小生成樹 $T$ 沒有這條邊。

那把 $e$ 加到 $T$ 上的話，會有一個環出現，我們叫他 $C$。原本那個 cut 把 $C$ 切開了，所以 $C$ 會有其他的 cut 上的邊。

所以把一條同時在 $C$ 上跟原本 cut 上的邊 $e'$ 丟了，它又變成一棵生成樹 $T'$。根據 $e$ 是原本 cut 上的最小邊，$T'$ 的權重一定比 $T$ 還小，矛盾。

大概觀察完問題的性質了。別忘記，我們的目標是在邊權都相異時，找到一棵 MST。

值得注意的是，在上面的兩個性質敘述裡，我們只看邊和邊之間的權重大小關係，就能決定哪條邊有沒有在 MST 裡了。甚至不用真的像比較兩個生成樹時那樣，需要把很多條邊的權重加起來！幾乎所有 MST 演算法都有這個性質。

以下介紹兩個適合初學的 MST 演算法。

我們似乎很在意邊和邊的關係。那如果把所有邊按照邊權大小排序，再從小到大，一條一條考慮要不要選進 MST 的話……

只看比目前邊權還小的邊，整張圖會形成好幾個連通塊。現在考慮加入這條邊，可以分成兩種情況：

1. 這條邊連接的兩個點屬於同個連通塊
   • 那有個環的最大邊是它！根據 cycle property，這條邊一定不在 MST 上，不能被加進來。
2. 這條邊連接兩個不同的連通塊
   • 那我們隨便切，只要把這兩個連通塊分開、同個連通塊放同一邊，cut 上的最小邊就是它。根據 cut property，這條邊一定在 MST 上，要被加進來。

和併查集在處理的問題根本就一模一樣！於是我們可以用併查集，對每條邊決定它要不要加進來，就找到一棵最小生成樹了。時間的瓶頸在排序，$O(M \log M)$。

struct DSU {
    int findDSU(int a);
    void unionDSU(int a, int b);
}; // 以上實作略
vector<array<int, 3>> E; // 存每條邊的 (邊權，點 u，點 v)

DSU dsu(n);
long long tot = 0;
sort(E.begin(), E.end()); // 用 array<int, 3> 的預設大小排序
for (auto [w, u, v] : E)
	if (dsu.findDSU(u) != dsu.findDSU(v)) {
		// 選這條邊進去 MST！
		tot += w;
		dsu.unionDSU(u, v);
	}

事實上，就算有邊權重複，這段程式還是能找到一棵 MST。排序就扮演著相同邊權的 tie-breaker；排完後，每條邊就已經被決定要不要選了。這帶給我們一個重要的結論：

繼續回來考慮邊權都相異的情況。找 MST 還有別種作法，我們換個角度思考，從某個起點 $s$ 開始，擴張屬於這個點的那棵樹。

具體來說，整個點集叫做 $V$ 好了，我們想維護的東西是和 $s$ 連通的集合 $U$。剛開始 $U$ 只有 $s$ 一個點、MST 是空的，每次尋找下一條連出 $U$ 且會在 MST 上的邊。根據 cut property，$U$ 和 $V \setminus U$ 之間權重最小的邊一定會滿足這個條件！每輪 $U$ 裡面會多一個點，做完 $N-1$ 輪後 $V \setminus U$ 是空的，我們就找到 MST 了。

這樣的過程中，每一輪需要挑出 $U$ 和 $V \setminus U$ 之間權重最小的邊。都檢查所有邊太慢了，所以我們對所有 $U$ 以外的點，紀錄它和 $U$ 中的節點之間，最小的邊權 $d$（我們把這個稱作它和 $U$ 的「距離」），每次挑出距離最短的。最無腦是暴力掃過所有點，這樣的時間複雜度是 $O(N^2+M)$。

但不難發現，我們是選出最小的點、用該點連出去的邊更新 $d$ 陣列。這過程和 Dijkstra's 演算法找最短路徑做的事非常像！可以一樣套用 priority queue 做到 $O(M\log M)$ 時間，理論上也一樣可以用 Fibonacci heap 達到 $O(N\log N + M)$。

using pii = pair<int, int>; // 存 (距離, 編號)
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<int> d(n, INT_MAX);
d[s] = 0;
pq.emplace(d[s], s);
ll tot = 0;
while (!pq.empty()) {
	auto [du, u] = pq.top();
	pq.pop();
	if (du != d[u])
		continue;
	tot += du; // 選這條邊加進 MST！
	d[u] = INT_MIN; // 標注 visited
	for (auto [v, w] : G[u])
		if (d[v] > w) {
            d[v] = w;
			pq.emplace(d[v], v);
        }
}

實際在程式比賽中的 Prim 當然不太可能有機會用 Fibonacci heap，所以用 priority_queue 做 Lazy deletion 的複雜度和 Kruskal 可以說是一樣的。不過，看似有點蠢的 $O(N^2+M)$ 作法，有些時候卻能勝過前兩者……

沒錯，當一張圖很稠密、$M=O(N^2)$ 時，這個作法會少一個 log！

以上介紹了兩種找 MST 的方法，大部分人在大部分情況都會選擇使用 Kruskal's algorithm，不過就算都是找 MST，對於不同的使用情境和題目性質，還是可能需要不同的方法；更別說還有其他種未提的 MST 演算法，以及更多其他在 MST 上可以問的問題了。一切都和 MST 最根本的數學結構有關，未來的章節中還會有許多篇幅介紹相關的主題，也很鼓勵讀者自行推導、理解看看。