Embedded Files
圖一(a)。
Intro
Intro
最小生成樹 Minimum Spanning Tree (縮寫: MST)
首先我們先定義生成樹 Spanning Tree
考慮一個connected、weighted的 undirected graph，如圖一(a)，在Graph上能夠定義Spanning Tree為：
連結所有Graph中的vertex的樹，見圖一(b)。
因為是樹，所以沒有cycle。
因為是樹，若Graph有V個vertex，Spanning Tree只有|V|−1條edge。
圖一(b)。
由於Graph具有weight，因此，不同的Spanning Tree，可能有不同的weight總和，而其中，具有最小weight總和的樹，稱為Minimum Spanning Tree(MST)，如圖一(c)。
圖一(c)。
小小提醒：
由於Graph的weight只要求要是實數(real value)，而且不要求每一條edge的weight必須唯一，因此，Graph中的MST可能不唯一。
由於MST的定義只要求「最小weight總和」，因此root是哪個vertex、樹是否平衡、height(樹高)是否夠小等等問題，皆不在必要的考慮範圍內。
演算法
演算法
在實作上，我們通常會使用兩種演算法來尋找最小生成樹
Kruskal's Algorithm
Kruskal's Algorithm
#想法:
當有兩棵MSS (Minimum Spanning Subtree) 時，合併兩棵MSS，選擇兩棵MSS之間最短的邊，顯然是最好的
當有三棵MSS時，以最小的邊連結的兩棵MSS先連結成一顆新的MSS，再連結第三棵，會是最好的
最一開始，每個點視為一棵MSS
不斷合併兩棵MSS，一直到最後變成一棵MST
合併時，不斷選擇最短的邊加入到樹裡面，直到最後變成一棵MST
#演算法:
排序所有的邊，由小到大
嘗試連結圖中最近的兩個點(選擇最短的邊)
如果兩個點已經位於同個MSS上，不理
如果兩個點位於不同MSS上，將兩個點位於的MSS合併成為新的MSS
重複2直到全部的點都位於同個MSS形成MST
#複雜度分析:
如果第一步使用STL的sort 複雜度: O(|E|log|E|)
連結MSS，如果使用 Disjoint Set 複雜度: O(Ea(V,E)) a為阿克曼函式的倒函式 證明有點複雜
整體複雜度O(|E|log|E|)
#證明
Disjoint Set 保證了每條邊都會是一個橋，因此 Kruskal 形成的圖會是一棵樹
Kruskal 共連結了 |V| - 1 條邊，每次選取的當下，都是連結兩個MSS中最小權重的邊
使用反證法，如果 Kruskal 上的一條邊E={s,t}並不存在於最小生成樹，s, t還是會需要被連結，而將E加入最小生成樹後，會形成一個環，環中一定有一條邊權重大於E，將E取代該條邊之後圖還會是一顆生成樹，而該生成樹的權重小於最小生成樹，這與最小生成樹的定義矛盾，因此Kruskal產生的樹就是最小生成樹。
Disjoint Set 並查集
通常支援兩種操作
Find
Union
所以又稱 Union-Find Tree
初始化
一開始還沒分團的時候，將每個節點當作一個集合，自己就是自己的父節點
#define MAX_N 1000
int d[MAX_N];
void initialize() {
for (int i = 0; i<MAX_N; i++) {
d[i] = i;
}
}
Find
接下來我們要找尋一個集合裡面，誰是老大 (root)，由於一個集合只會有一個老大，所以可以用老大當作集合的代表
int Find(int x) {
if (d[x] != x) {
return Find(d[x]);
}
return x;
}
在找尋根的同時
我們順便把路上遇到的節點的父節點，設為老大 (root)
節省之後找尋老大的時間
int Find(int x) {
if (d[x] != x) {
return d[x]=Find(d[x]);
}
return x;
}
Union
要合併兩個集合xy，要重新選擇一個老大
最簡單的方法，就是將x集合的老大帶著小弟，全部投靠到y集合的隨便一個人身上
這樣所有x集合原本的成員，就會視y的老大為自己的老大
void Union(int x,int y){
x = Find(x);
d[x] = y;
}
修改程式碼讓x直接投靠y的老大
能讓樹的深度更小，查詢更快
void Union(int x,int y){
x = Find(x);
y = Find(y);
d[x] = y;
}
這邊需要注意的是，函數名稱請不要設成 union
因為 union 在 C++ 中是保留字，重複的話會出錯
另一個需要注意的是
這邊到底是要讓x投靠y 還是y投靠x
這邊有幾種方法，根據不同題目會有不同的答案
x投靠y
編號小的投靠編號大的
集合成員小的投靠集合成員多的
不過我目前沒有遇到需要用到後兩個的題目，只是有耳聞這三種常見的方法而已
如果有遇到的話我會再補充
將程式碼精簡化之後，完整的程式碼會長這樣
#define MAX_N 1000
int d[MAX_N];
void initialize() {
for (int i = 0; i<MAX_N; i++)
d[i] = i;
}
int Find(int x) {
return d[x] == x ? x : d[x] = Find(d[x]);
}
void Union(int x, int y) {
d[Find(x)] = Find(y);
}
有了這項資料結構
我們就能處理之前說到檢查兩棵MSS是否有合併過了
只要將邊連結的兩個節點
檢查兩個節點是否屬於相同的Disjoint Set裡面就好了
Prim's Algorithm
Prim's Algorithm
#演算法:
1.任意選擇任何一個點當作根( Root )。
2.選擇此點周圍權重最小的邊( Edge )，然後將這條邊的另外一點( Node )加入原來的點集合。
3.仿照1和2的概念，考慮點集合裡面的點所連接的邊，且滿足邊的另外一點並不在點集合裡面，選擇最小權重的邊，將此邊另外一點加入點集合。
4.重複動作3，直到全部點被加入為止。
#複雜度分析:
步驟1 選任意點當根 O(1)
步驟2 如果使用STL的 priority_queue 來找到當前權重最小的邊 O(logV)，此步驟共會執行 V 次，所以複雜度為 O(VlogV)
步驟3中 會找點所連結的邊，由於總共的邊如果使用 adjacency list 總共會有 2|E|條邊 複雜度 O(E)
整體複雜度 O(E + VlogV) = O(VlogV)
由於給定的圖並不是樹 (如果是樹的話 |E| = |V| -1) ，如果給的是樹那最小生成樹也不用求了，因為該圖的生成樹唯一
假設給定的圖不是樹 |E| >= |V|
所以使用 Prim O(VlogV) 複雜度會低於 Kruskal O(ElogE)
根據步驟2和3的資料結構不同 Prim 的複雜度會有很大的差異
#證明
證明我們主要使用反證法
一開始選擇最小的邊E，該邊一定會是最小生成樹的其中一個邊
如果E不存在於最小生成樹，將E加入最小生成樹一定會形成一個環，將E取代環中比E權重大的邊E'，使得新的最小生成樹權重更小，違反最小生成樹的定義
假設已經有一個MSS，將MSS中所有連到的邊，取最短的邊E連結一個新的節點，E一定會是最小生成樹的其中一個邊
與步驟1的反證同理，如果以E取代MST中形成環的一個邊E'使得權重更小，會與最小生成樹的定義矛盾
綜上，Prim產生的生成樹是最小生成樹
#實作建議:
1.將所有點根邊儲存起來
2.利用以上想法，並建立一個名為 Visit 的 bool 陣列(或 bitset )儲存點「是否」在點集合
3.過程中的最小權重的邊用 Priority Queue 維護。
練習1: a129: 最小生成樹
練習2: c495: 四、次小生成樹(SBMST) 詳解
作業: The Unique MST (上傳時Language請選擇"G++"，並且POJ不能使用"bits/stdc++.h"，以及sort()中不能使用lambda (參考)
各種其他生成樹 (網站程式碼有些有錯誤)
各種其他生成樹 (網站程式碼有些有錯誤)
有向圖最小生成樹 Edmonds' Algorithm (待補)
Google Sites
Report abuse