1. 建生成樹之 Kruskal 演算法

2021-06-06 21:19:10 +0800 CST Tags: disjoint-set, m.s.t

問題：給定一張連通的有權無向圖 (weighted undirected graph) $G$，請求出該圖的最小生成樹 (minimum spanning tree, MST)。

解法：先對所有的邊按照權重由小到大排序。接著由最小的邊開始看，如果該條邊的加入並不會讓建構中的生成樹內產生環 (cycle) 的話，就必須把它加進樹裡。那所有的邊都看過之後，結果子圖 (subgraph) $T$ 就是答案。

證明：

Kruskal 演算法結束後的子圖 $T(V,E)$ 必為生成樹 (a: 所有的頂點都落在 $T$ 內、b: $T$ 必須連通而且 c: 沒有環)。
假設違反 (a)，那必定至少有一個點 $v$ 其鄰接的所有邊 $e(v, v')$ 都無法被加進 $E$，根據我們選邊的條件，這代表每次其中任一條邊的加入都會造成環的產生，而這個環必定包含 $v$，這同時意味著 $v$ 早已落在建構中的 $T$ 內，與假設矛盾。假設違反 (b)，那 $T$ 必定至少可以剖分成兩個以上彼此互不連通的連通元件，令其中兩個為 $T_A$ 和 $T_B$，那麼因為原圖是連通的，它們之間必定有一條邊 $e\in G$ 能連接彼此，如果這個邊沒有被選中，這意味著它的加入會使得建構中的 $T$ 產生環，而這只會在當 $T_A$ 和 $T_B$ 已經在 $T$ 裡連通的時候發生，與原假設不符產生矛盾。至於 (c) 是最不可能違反的，因為在選邊的過程中隨時都保持 $T$ 沒有環的狀態，演算法結束後當然也不可能會有。
上述結論告訴我們每個 $G$ 都至少有一個演算法能順利找到一棵生成樹，於是每個 $G$ 都至少有一棵生成樹，下面的 $T^*$ 一定存在。
如果 $G$ 有兩棵以上的生成樹，要怎麼確保 Kruskal 找到的權重和會最小呢？
我們的證明手法如下，令演算法在每個階段選邊後形成的樹為 $T_1$、$T_2$、⋯⋯、$T_i$，最後得到 $T=T_{|E|}$，而 $T^*$ 是其中一棵只有神才知道的正確答案，那我希望在從 $T^*$ 漸漸調整到 $T$ 的過程中都還是一棵生成樹而且保持權重和的 (不嚴格) 遞減性，那因為 $T^*$ 已有最小權重和了，所以 $T$ 也必須有最小權重和，換言之 Kruskal 演算法找到的生成樹是正確的。本證明中我們檢查邊的順序和 Kruskal 並無不同，都是從最小的邊 $e_1$ 開始看，第 $i$ 回合看到第 $i$ 條邊 $e_i$，令一開始調整前的樹為 $T^*_0=T^*$，而每次第 $i$ 回合我們都會從 $T^*_{i-1}$ 調整為 $T^*_i$，這個調整規則會保證 $T^*_i$ 對於 $e_1$、$e_2$、⋯⋯、$e_i$ 這些邊的包含關係會和 $T_i$ 一模一樣，換句話說如果只看 $e_i$ 以前的邊的話 $T^*_i$ 和 $T_i$ 會相等。每個回合一開始的待調整邊 $e_i\in G$ 在兩棵樹 $T_i$、$T^*_{i-1}$ 的包含關係可以歸納為以下三種情況分別討論：(a) 同時被兩棵樹包含或不包含，這個情況不需要調整，繼續往下一條邊看；(b) 只被 $T^*_{i-1}$ 包含，這種情況不可能會發生，因為根據生成樹的特性 $e_1$ 到 $e_i$ 裡面有被 $T^*_{i-1}$ 包含的邊沒辦法構成一個以上的環，再搭配我們的調整順序前提，$e_1$ 到 $e_{i-1}$ 在 $T_{i-1}$ 和 $T^*_{i-1}$ 的包含關係要完全相同，於是對 Kruskal 演算法來說 $e_i$ 的加入也不會讓過程中的 $T_i$ 產生環，它必須選入 $e_i$ 這條邊，換言之 $T_i$ 必須包含 $e_i$；(c) 只被 $T_i$ 包含，這個情況才是重頭戲，我們想證明在這種情況下 $T^*_{i-1}$ 總是包含一條比 $e_i$ 還要大的邊 $e_j\ (j>i)$ 可以被取代掉，使得調整後的新圖 $T^*_i:=T^*_{i-1}\cup\{e_i\}\setminus{\{e_j\}}$ 仍是最小生成樹，這其實用反證法即可說明，先考慮 $T':=T^*_{i-1}\cup\{e_i\}$，根據生成樹 $T^*_{i-1}$ 原本就連通的特性，加上一條邊後的 $T'$ 至少有兩個頂點 $u$ 和 $v$ 之間有兩條不同的路徑，換言之 $T'$ 一定有環而且是唯一的，否則任兩個環合併之後扣掉 $e_i$ 就是一個可以被 $T^*_{i-1}$ 包含的環，這與生成樹不包含環的性質不符，讓我們姑且稱這個唯一的環為 $C$，而事實上就是這個 $C$ 必須包含至少一條比 $e_i$ 還要大的邊 $e_j\ (j > i)$，那為什麼用反證法就能說明？若 $C$ 都只包含那些不比 $e_i$ 大的邊 $e_j\ (j\le i)$，根據我們的調整順序前提 $T_i$ 就必須包含 $C$，但這違反了演算法選邊的規則，於是得證 $T'$ 必定包含一條比 $e_i$ 還要大的邊 $e_j\ (j>i)$ 可以被取代掉，我們可以放心地建構另一棵權重和不超過 $T^*_{i-1}$ 的 $T^*_i:=T'\setminus{\{e_j\}}$。那不放心的讀者可以再度驗證 $T^*_i$ 仍是一棵生成樹：(a) 因為我們是拿掉環裡面的一條邊，而環上每個頂點都會接觸至少兩條以上的邊，所以經過取邊後的每個頂點都還是能接到至少一條邊，$T^*_i$ 會包含所有頂點；(b) 原本有環的 $T'$ 上任兩點 $u$ 和 $v$ 之間至少會有一條路徑 $P$ 連接，對於 $P$ 上每段通過 $C$ 的子路徑 $P_i$，如果它剛好有路過那條被取代的邊 $e_j$，我們可以立即將其改道至通過 $C\setminus{\{e_j\}}$ 的那一邊而仍然不影響 $P_i$ 的連通性，於是改道後的 $P$ 仍然能負起連接 $u$ 和 $v$ 的責任，$T^*_i$ 仍能保持連通；(c) 最後因為環的數量是由一減至零，$T^*_i$ 沒有環也是理所當然的。

補充：生成樹 $T$ 的邊數 $|E(T)| = |V| - 1$。

證明：可以把生成樹的每條邊都視為是把過程中的 $T$ 的某兩個連通分量合併成一個的過程，否則就會出現環。那麼一開始原圖 $G$ 有 $|V|$ 個點，即 $|V|$ 個互不連通的連通分量，每增加一條邊就會減少一個連通分量，而因為最後 $T$ 是連通並且包含了所有 $G$ 的頂點，它的連通分量數必為 $1$，於是從 $|V|$ 到 $1$ 的這個差距就是 $|V|-1$。

備註：這個演算法對 $G$ 的要求僅如原問題所述，一條邊可以連接同一個頂點，任意兩頂點之間也可以有多條邊連接，邊權重也可以是任意負數。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int V=, E=; // V:=點數、E:=邊數
int p[V], x[E], y[E], w[E], id[E];

int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }

int ans = 0;
for (int i=0; i<V; i++) p[i] = i;
for (int i=0; i<E; i++) id[i] = i,
    cin >> x[i] >> y[i] >> w[i];
sort(id, id+E, [](int a, int b) { return w[a] < w[b]; });
V--; // 還剩下 V-1 條邊可以用
for (int i=0; i<E && V; i++) {
    int x2 = find(x[id[i]]), y2 = find(y[id[i]]);
    if (x2 != y2)
        p[x2] = y2, ans += w[id[i]], V--;
}
if (!V) cout << ans << '\n'; // V-1 條邊都用完代表整張圖連通
else cout << -1 << '\n'; // 邊沒用完則一定不連通