acm/course/MST

#MST (Minimum Spanning Tree, 最小生成樹) ##Spanning Tree (生成樹) 1. 一棵包含圖上所有點的樹，稱作該圖的生成樹

2. 一張圖的生成樹可能會有很多種

3. 完全連通圖才有生成樹 (不連通時，則稱為生成森林)

4. 生成樹的權重為樹上每條邊的權重總和

##Minimum Spanning Tree 擁有最小權重的生成樹，稱為最小生成樹

###Kruskal’s algorithm (greedy based) 1. 依照權重排序

2. 選擇較小的邊，並邊檢查是否有迴圈

• Psuedocode

KRUSKAL(G):
 A = ∅
 foreach v ∈ G.V:
    MAKE-SET(v)
 foreach (u, v) in G.E ordered by weight(u, v), increasing:
    if FIND-SET(u) ≠ FIND-SET(v):
       A = A ∪ {(u, v)}
       UNION(u, v)
 return A

• 時間複雜度 O(ElgE)

###Prim’s algorithm (relaxation based) 1. 所有節點設為未拜訪過

2. 令d[i]為到節點i的目前距離，起使皆設為INF

3. 每次都去找未拜訪過的節點i，而且d[i]最小

4. 找完後要更新未拜訪過的節點距離d[j] ( if(找到的節點i到節點j的距離<d[j]) 則更新d[j] )

*時間複雜度 O(𝑉")

With Binary-Heap : O( (V+E) lgV)

參考來源：演算法筆記 http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html