程式扎記: [ Alg info ] Kruskal’s algorithm (MST)

標籤

2013年4月30日 星期二

[ Alg info ] Kruskal’s algorithm (MST)

Preface: 
Kruskal 演算法是一種用來尋找 MST(minimum spanning tree) 的演算法,由 Joseph Kruskal 在1956年發表。用來解決同樣問題的還有 Prim演算法 和 Boruvka演算法等。三種演算法都是 貪婪演算法 的應用。和 Boruvka演算法 不同的地方是,Kruskal演算法 在圖中存在相同權值的邊時也有效. 

Description: 
一般常見的 MST 演算法會採用下面的 pseudo code: 
  1. GENERIC-MST(G,w)  
  2. while A does not form a spanning tree  
  3.     find an edge (u,v) that is safe for A  
  4.     A=A⋃{(u,v)}  
  5. return A  
接著解釋一下上面的 pseudo code: 
* A 用來存放 MST edge 的 set.
* "find an edge (u,v) that is safe for A" 指的是加上該 edge 後, 不會讓 A 中的 forest 形成 loop (acyclic).
* "A=A⋃{(u,v)}" 指把 edge (u,v) 加到 A 中.

也就是說這個 pseudo code 會: 
* A 是最終的 MST 的edge的subset
* 隨時 A 都保持acyclic (No cycle)
* 每次都選一個edge, 把 A 形成的 graph 中兩棵 tree 連接起來 (因為不能出現cycle)
* 最後共選|V|-1條邊

Kruskal’s algorithm: 
要開始講這個演算法前, 為了要看懂它的 pseudo code, 先要來知道會用到的 routine: 
* MAKE-SET(v): 創造一個set 包含 v.
* FIND-SET(v): 找到set 包含 v.
* UNION(u,v): 把兩個set合併起來

接著是該演算法的 pseudo code: 
  1. MST-KRUSKAL(G,w)  
  2. A={}  
  3. for each vertex v∈G.V  
  4.     MAKE-SET(v)  
  5. sort G.E by w  
  6. for each edge (u,v) ∈G.E  
  7.     if FIND-SET(u)≠FIND-SET(v)  
  8.         A=A⋃{(u,v)}  
  9.         UNION(u,v)  
  10. return A   
接著簡單說明如下: 
1. 初始時, 每個 vertex 各自屬於一個 set
2. 接著對 Graph 的 edge's weight 進行 sorting (從小到大)
3. Loop edges
3.1 如果該 edge(u,v) 的 u 與 v 分屬不同的 set, 則將該 edge 加到 A
3.2 將分屬於 u 與 v 的 set 進行 union.

Example: 
接著我們來看一個範例, 考慮有 Graph 如下: 
 
1. Sorting 過後, 第一個取出來的 edge(0,5). 因為 vertex 0, 5 分屬不同的 set, 故將此 edge 加到 A 
 

2. 接著第二個取出來的 edge(2,3). 因為 vertex 2, 3 分屬不同的 set, 故將此 edge 加到 A 
 

3. 接著第三個取出來的 edge(1,6). 因為 vertex 1, 6 分屬不同的 set, 故將此 edge 加到 A 
 

4. 接著第四個取出來的 edge(1,2). 因為 vertex 1, 2 分屬不同的 set, 故將此 edge 加到 A 
 

5. 接著第五個取出來的 edge(3,6). 因為 vertex 3, 6 屬於同一個 set {(1,2), (1,6), (2,3)}, 故捨棄此 edge! 
 

6. 接著第六個取出來的 edge(3,4). 因為 vertex 3, 4 分屬不同的 set, 故將此 edge 加到 A 
 

7. 接著第七個取出來的 edge(4,6). 因為 vertex 4, 6 屬於同一個 set {(1,2), (1,6), (2,3), (3,4)}, 故捨棄此 edge! 
 

8. 接著第八個取出來的 edge(4,5). 因為 vertex 4, 5 分屬不同的 set, 故將此 edge 加到 A; 且此時 A 有 6 個 edges = |V|-1. 故 MST 已經完成
 

Supplement: 
[ Alg info ] Borůvka's algorithm (MST) 
[ Data Structures with Java ] Section 25.6 : Minimum Spanning Tree 
[ 資料結構 小學堂 ] 圖形結構 : 擴張樹 (Prim) 
[ 資料結構 小學堂 ] 圖形結構 : 擴張樹 - 求最小成本擴張樹 (Kruskal 演算法)

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!