4.3.1 - Kruskal's algorithm

$G=(V, E)$

Steps:

1. 自 $E$ 中挑出最小成本的邊 $(u, v)$

   $\Rightarrow$使用Heap的Delete-Min()，花 $O(logE)$

2. 判斷$(u, v)$ 加入spanning tree中，是否會形成cycle

   1. 是: 放棄

   2. 否: 將(u, v)加入S中

   $\Rightarrow$使用Disjoint Set(互斥集)來判斷是否會產生cycle

   if (find(u) != find(v){ //判斷u, v是否屬於同一個集合

   ​union(u, v); //將u, v聯集加入S中

   }

3. 重複1~2直到已挑出$v-1$ 個邊或是E為空

若 $S$的邊數小於$v-1$ ，則 $G$ 無spanning tree。

Time: $O(ElogE)$

e.g.

1. 挑出(1, 6)

   
2. 挑出(3, 4)

   
3. 挑出(2, 7)

   
4. 挑出(2, 3)

   
5. 挑出(4, 7)會形成cycle

6. 挑出(4, 5)

   
7. 挑出(5, 7)會形成cycle

8. 挑出(5, 6)

   

Min Cost = 99