[Algorithm Cheat sheet] Minimum Spanning Tree

1. Basic concept about Spanning Tree and M.S.T
2. Kruskal’s Algorithm to find MST
3. Prim’s Algorithm to find MST
4. Sollin’s Algorithm to find MST

Basic Concept about Spanning Tree

給予一個 "Connected" 的undirected graph，其Spanning Tree .S=(V , T)為其子圖，且滿足 :

1. |E| = |T|+ |B| ( T: tree edge,B: back edge)
2. 若自B中任選一邊加入S必定會形成Cycle。
3. 在S中，任何"頂點對"之間只存在一條Simple Path
4. Graph 中有許多棵 Spanning Tree.
5. Spanning Tree的邊數必為 |T|=n - 1 (跟Tree的特性一樣)

DFS spanning tree.

Minimum Spanning Tree

擁有最小cost/weight的Spanning Tree 即為Minimum Spanning Tree (M.S.T)

1. MST 可能 ≥ 1 棵
2. 除非每個edge cost皆不相同，才有可能會有唯一的MST。

Note:
(1)If edge(u,v)是G中weight最小的邊，則edge(u,v)必在Graph中的某一個MST中
(2)If edge(x,y)是G中weight第二小的邊，則edge(x,y)必在Graph中的某一個MST中

Remark Table :

╔═══════════╦═════════════════════╦════════════════╦══════════════╗
║ Opeartion ║     Time  cost      ║ Data Structure ║   Strategy   ║
╠═══════════╬═════════════════════╬════════════════╣══════════════╣
║ Kruskal's ║ O(ElogE) or O(ElogV)║                ║    Greedy    ║
╠═══════════╬═════════════════════╬════════════════╣══════════════╣
║   Prim's  ║       O(V^2)        ║Adjacency matrix║    Greedy    ║
╠═══════════╬═════════════════════╬════════════════╣══════════════╣
║   Prim's  ║       O(VlogV+E)    ║ Fibonacci-heap ║    Greedy    ║
╠═══════════╬═════════════════════╬════════════════╣══════════════╣
║  Sollin's ║       O(ElogV)      ║                ║    Greedy    ║
╚═══════════╩═════════════════════╩════════════════╝══════════════╣

Kruskal’s Algorithm

STEPS :

1. 將所有的edges依照weight由小到大排好 ... O(ElogE)
2. 迭代所有的edge(in non-decreassing order)
如果加入此邊對於目前的形勢 "不會形成cycle" 的話，便加入此邊，否則就不加入。
3. 重複step#2 直到有(V-1)個edges在此Spanning Tree.

Prim’s Algorithm

STEPS :

1. 選出"最小成本"的edge(u,v)，其中 u ∈ U，v ∈ U-{u}
2. 加入edge(u,v)至Spanning Tree中，且將 v 自U-{u}集合中移出並加入U中
3. 重複step#2 直到 U=V 或是 已經沒有edge可以選了。

Improved Prim’s Algorithm

Sollin’s Algorithm

STEPS :

0.一開始，將每個頂點是為獨立tree之root
1. 從每棵Tree排出最小成本的tree edge
2. 刪除重複排出的tree edge，只留一份即可。
3. 重複step#1,#2 直到有只剩一棵tree 或 沒有edge可以加了
4. 如果|T|<|V|-1，則NO Spanning Tree.