spanning tree / spanning forest

「生成樹」。從一張圖取出一棵樹，包含圖上所有點。可能有許多種。

當一張圖完全連通，則擁有生成樹。當一張圖不連通，則沒有生成樹，而是擁有許多棵「生成子樹」構成的「生成森林」。

生成樹的權重，是樹上每條邊的權重總和。

minimum spanning tree

「最小生成樹」。權重最小的生成樹。可能有許多種。

用途

求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。

想法

一、一個單獨的點，視作一棵最小生成子樹MSS。

二、兩棵MSS連結成一棵MSS，以兩棵MSS之間權重最小的邊進行連結，顯然是最好的。

三、三棵MSS連結成一棵MSS，以其中兩棵MSS之間權重最小的邊進行連結，才連結第三棵，總是比較好。

點的視角：不斷連結兩棵MSS、合併兩棵MSS，得到最小生成樹（森林）。

邊的視角：依序以權重最小、次小、……的邊，嘗試連結各棵MSS，得到最小生成樹（森林）。

演算法

一、圖上每一個點，各自是一棵最小生成子樹MSS。
二、圖上所有邊，依照權重大小，由小到大排序。
三、嘗試圖上所有邊，作為最小生成樹（森林）的邊：
　甲、兩端點分別位於兩棵MSS，也就是產生了橋：
　　　用這條邊連結兩棵MSS，合併成一棵MSS。
　　　這條邊是最小生成樹（森林）上的邊。
　乙、兩端點皆位於同一棵MSS，也就是產生了環：
　　　捨棄這條邊。

尋找最小生成樹的過程：

尋找最大生成樹的過程：

時間複雜度

一、排序圖上所有邊。O(ElogE)。

二、連結MSS，採用「disjoint-sets forest」。O(Eα(V))。

總時間複雜度O(ElogE)。

如果兩點之間有多條邊，預先以graph traversal掃描一次所有邊，保留權重最小的邊，仍可求得正確答案。兩點之間只剩下一條邊，邊數至多C(V,2) = V(V-1)/2 = O(V²)條。時間複雜度O(ElogE)可以改寫成O(ElogV²) = O(2ElogV) = O(ElogV)。

const int V = 100, E = 1000; struct Edge {int a, b, c;} e[E]; // edge list bool operator<(Edge e1, Edge e2) {return e1.c < e2.c;} // disjoint-sets forest int p[V]; void init() {for (int i=0; i<V; ++i) p[i] = i;} int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));} void merge(int x, int y) {p[find(x)] = find(y);} void Kruskal() { init(); // 圖上所有邊，依照權重大小，由小到大排序。 sort(e, e+E); // 依序找出最小生成樹上的V-1條邊。 int i, j; for (i = 0, j = 0; i < V-1 && j < E; ++i) { // 產生環，則捨棄。直到產生橋。 while (find(e[j].a) == find(e[j].b)) j++; // 產生橋，則以此邊連接兩棵MSS。 merge(e[j].a, e[j].b); // 印出最小生成樹（森林）上的邊。 cout << "起點：" << e[j].a << "終點：" << e[j].b << "權重：" << e[j].c; j++; // 別忘記累計索引值。也可以寫入迴圈。 } if (i == V-1) cout << "得到最小生成樹"; else cout << "得到最小生成森林"; }

迴圈的部份也可以寫成這樣。

// 窮舉圖上所有邊，嘗試作為最小生成樹（森林）。 for (i = 0, j = 0; i < V-1 && j < E; ++j) { // 產生環，則捨棄。 if (find(e[j].a) == find(e[j].b)) continue; // 產生橋，則以此邊連接兩棵MSS。 merge(e[j].a, e[j].b); // 印出最小生成樹（森林）上的邊。 cout << "起點：" << e[j].a << "終點：" << e[j].b << "權重：" << e[j].c; i++; // 別忘記累計索引值。不可以寫入迴圈。 }

UVa 908 10369

用途

求出無向圖的其中一棵最小（大）生成樹。

演算法

仿效Dijkstra's algorithm。

差異：Dijkstra's algorithm屢次找不在樹上、離根最近的點，Prim's algorithm屢次找不在樹上、離樹最近的點。

另一個差異：選擇特定一點作為起點，得到不同的最短路徑樹；選擇任意一點作為樹根，得到相同的最小生成樹。

時間複雜度

圖的資料結構為adjacency matrix是O(V²)；圖的資料結構為adjacency lists仍是O(V²)。

如同Dijkstra's algorithm，運用各種極值資料結構得以降低時間複雜度。

int adj[9][9]; // adjacency matrix int d[9]; // 記錄目前的MST到圖上各點的距離 int parent[9]; // 記錄各個點在MST上的父親是誰 bool visit[9]; // 記錄各個點是不是已在MST之中 void prim() { for (int i=0; i<9; i++) visit[i] = false; for (int i=0; i<9; i++) d[i] = 1e9; // 選擇任意一點作為樹根。此處選擇第零點作為樹根。 d[0] = 0; parent[0] = 0; for (int i=0; i<9; i++) { // 找不在樹上、離樹最近的點。 int a = -1, b = -1, min = 1e9; for (int j=0; j<9; j++) if (!visit[j] && d[j] < min) { a = j; // 持續記錄最近的點 min = d[j]; } // 從起點可連通的點已經找完 if (a == -1) break; visit[a] = true; // relaxation // 此處與Dijkstra's algorithm不同 // 離樹最近，不是離根最近。 for (b=0; b<9; b++) if (!visit[b] && adj[a][b] < d[b]) { d[b] = adj[a][b]; parent[b] = a; } } }

UVa 10034 10147 10307 10397 10842

© 2010 tkcn. All rights reserved.

用途

求出無向圖的其中一棵最小（大）生成樹。若是圖不連通，則是求出其中一叢最小（大）生成森林。

演算法

一、圖上每一個點，各自是一棵最小生成子樹MSS。
二、每棵MSS同時找權重最小、索引值最小的聯外邊，相互連接。
　口、聯外邊是MSS之間的邊，不是MSS之內的邊。
　口、聯外邊可能重複，無妨。
　口、聯外邊顯然不會形成環。
三、重複步驟二，直到形成最小生成樹（森林）。

找權重最小的聯外邊，以得到最小生成樹；當權重一樣小，則找索引值最小的聯外邊，以避免聯外邊形成環。聯外邊的索引值，可以改成聯外邊的兩端點索引值。

證明很簡單：圖上任意一個環，環上權重最大、索引值最大的邊，絕不會被選中。過程中無法形成環，只會形成樹。每一點都聯外，權重又最小，所以是最小生成樹。

時間複雜度

一、每回合尋找權重最小、索引值最小的聯外邊。O(V+E)。

二、連接MSS。採用「disjoint-sets forest」，每回合每個點都呼叫了merge與find，森林結構維持在最佳狀態，merge與find的總時間複雜度，從O(Eα(V))降為O(E)。

三、回合數。最差情況：每回合MSS兩兩成對互連，MSS總數量僅下降一半，共logV個回合。平均情況：圖上的邊呈隨機分布，僅1至2個回合。【待補證明】

最差時間複雜度O((V+E)logV)，通常簡單寫成O(ElogV)。平均時間複雜度O(V+E)。

const int V = 100, E = 1000; struct {int a, b, c;} edge[E]; // edge list int d[V]; // 各棵MSS的最小聯外邊的權重 int e[V]; // 各棵MSS的最小聯外邊的索引值 // disjoint-sets forest int p[V]; void init() {for (int i=0; i<V; ++i) p[i] = i;} int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));} void merge(int x, int y) {p[find(x)] = find(y);} void Borůvka() { init(); while (true) { int cross_edge = 0; for (int i=0; i<V; ++i) d[i] = 1e9; for (int i=0; i<E; ++i) { int a = find(edge[i].a); int b = find(edge[i].b); int c = edge[i].c; if (a == b) continue; cross_edge++; if (c < d[a] || c == d[a] && i < e[a]) d[a] = c, e[a] = i; if (c < d[b] || c == d[b] && i < e[b]) d[b] = c, e[b] = i; } if (cross_edge == 0) break; for (int i=0; i<V; ++i) if (d[i] != 1e9) merge(edge[e[i]].a, edge[e[i]].b); } }

用途

求出有向圖的其中一棵最小（大）生成樹。

有向圖上，以權重最小的邊，連結兩棵有向MSS，不見得形成有向MSS。直接套用無向圖的演算法，邊的方向亂七八糟，無法形成有向生成樹。必須設計其他演算法。

想法

生成樹的基本概念是：連接圖上各點的樹。從這個概念下手，並且考慮邊的方向性，得到兩個粗糙的演算法：

有向圖上，每一個點，如果要被連結到，都要至少有一條出邊，除了樹葉以外。
每一個點，找權重最小的出邊，會比較好。

有向圖上，每一個點，如果要被連結到，都要剛好有一條入邊，除了樹根以外。
每一個點，找權重最小的入邊，會比較好。

出邊有許多條，入邊只有一條，從入邊下手比較容易。

樹根是個例外，樹根沒有入邊。但是我們可以假定我們已經知道最小生成樹的樹根是哪個點，如此就不必顧慮例外了。設計好演算法之後，用試誤法嘗試各種樹根即可。

minimum arborescence

預先指定樹根的有向最小生成樹。個人感覺這個詞彙不太討喜。

水母【尚無正式名稱，因為像水母就把它叫做水母】

運氣好的時候，各點的最小入邊，剛好形成一棵生成樹，而且是最小生成樹。

運氣普通的時候，各點的最小入邊，通常形成許多隻水母。

各點各取一條入邊，一旦入邊們形成環，此環一定只有出邊、沒有入邊。環與出邊，形成一個特別的圖：很多棵樹，一個環串起了樹根。又像是太陽、又像是水母。

把水母改裝成最小生成子樹

最小生成樹不得有環。水母有環，是不合格的。

水母是權重最小的連結方式，最小生成樹的權重則略高、等高於水母。使用窮舉法，嘗試拆除水母的每一條邊，並且更改為另一條邊，從中找到權重增加最少的邊。

一、更改水母環的邊：
　甲、新邊是由其他水母連入：水母環消失。變成其他水母腳。很好！
　乙、新邊是由自身水母環連入：水母環變小。連結權重無故變大，不可取。
　丙、新邊是由自身水母腳連入：水母環變大。多了一些點可供聯外。
二、更改水母腳的邊：
　　水母環不變，連結權重無故變大，不可取。

有好處的只有一甲、一丙。歸納出：只需要更改水母環的邊，讓水母環消失或者變大，從中選擇權重增加最少的拆除方式。

演算法

水母環的入邊，全部看過一遍，找到權重增加最少的入邊。

已經看過的入邊，修改成權重增加量，然後收縮水母環，就不用看第二遍了。

壹、刪去所有自環：自己連向自己的邊。
貳、圖上每一點嘗試作為樹根。
　一、刪去樹根的全部入邊。也可以將權重設定為無限大。
　二、判斷樹根能不能連到圖上各點。否則生成樹不存在。
　三、重複以下步驟，直到形成生成樹為止：
　　甲、每一個點，找出權重最小的入邊。O(V+E)
　　　　形成一群水母。
　　乙、調整水母環的入邊的權重，修改成權重增加量。O(V+E)
　　　　w(a, x) -= w(å, x)，
　　　　x是水母環上一點。
　　　　åx是x點的最小入邊，也是水母環上的邊。
　　　　ax是x點的其他入邊。
　　丁、收縮水母環，成為一點。O(V+E)

Kruskal's algorithm連結多個MSS。一旦發現造成環的邊，就直接捨棄；一旦發現造成橋的邊，就一定保留。

Edmonds' algorithm連結多隻水母。總是留下造成環的邊（形成水母環），並且嘗試各種打開環的方式：有時候擴大水母環，有時候兩隻水母連結成一隻水母。

時間複雜度

一、每回合找出各點的最小入邊。O(V+E)。

二、回合數。最差情況是每回合產生一個水母，水母環只有兩點。水母環收縮之後，整張圖只減少一個點。圖上有V個點，最多收縮V-1次水母環，總共V-1個回合。

三、窮舉V個點，嘗試作為樹根。

時間複雜度O(VVE)。

const int V = 100, E = 1000; struct Edge {int a, b, c;} edge[E]; // edge list int d[V]; // 每個點最小入邊的權重 int p[V]; // 每個點最小入邊的來源 int v[V]; // 拜訪過 int n[V]; // 水母環 int m[V]; // 已收縮 int edmonds(int r) // 指定樹根 { memset(m, 0, sizeof(m)); int w1 = 0; // 目前生成樹的權重 int w2 = 0; // 累計收縮水母環而失去的權重 for (int k=0; k<V-1; k++) { /* O(E) graph traversal. find minimum in-edge for each vertex. --->o */ memset(d, 1, sizeof(d)); memset(p, -1, sizeof(p)); for (int i=0; i<E; ++i) { int& a = edge[i].a; int& b = edge[i].b; int& c = edge[i].c; if (a == b) continue; if (b != r && c < d[b]) d[b] = c, p[b] = a; } /* O(V) jellyfish detection ___ / \ \___/ _/|||\_ //1\\ */ memset(v, -1, sizeof(v)); memset(n, -1, sizeof(n)); w1 = 0; bool jf = false; for (int i=0; i<V; ++i) { if (m[i]) continue; if (p[i] == -1 && i != r) return 1e9; if (p[i] >= 0) w1 += d[i]; // 找水母環 int s; for (s = i; s != -1 && v[s] == -1; s = p[s]) v[s] = i; // 標記水母環上的點，以及將會被收縮掉的點。 if (s != -1 && v[s] == i) { jf = true; int j = s; do { n[j] = s; m[j] = 1; w2 += d[j]; j = p[j]; } while (j != s); m[s] = 0; } } if (!jf) break; // 一旦形成生成樹就停止 /* O(E) edge reweighting and cycle contraction ___ / \ <- \___/ */ for (int i=0; i<E; ++i) { int& a = edge[i].a; int& b = edge[i].b; int& c = edge[i].c; if (a == b) continue; if (n[b] >= 0) c -= d[b]; if (n[a] >= 0) a = n[a]; if (n[b] >= 0) b = n[b]; } } return w1 + w2; }

演算法

窮舉樹根，再仿效Dijkstra's algorithm，時間複雜度O(V³)。有差異的地方，不影響時間複雜度：

一、縮環最多V-1次（兩點縮成一點）。縮環得到的新點，最多V-1個。總點數最多2V，仍是O(V)。

二、縮環，採用disjoint-sets forest。O(Eα(V))。

如同Dijkstra's algorithm，運用各種極值資料結構得以降低時間複雜度。

UVa 11183