前言

昨天介紹了Mininum spanning tree，找Mininum spanning tree的方法有Kruskal's Algorithm和Prim's Algorithm，今天先介紹Kruskal's Algorithm。

註: Borůvka's Algorithm 也是找Mininum spanning tree的方法，這三種方法較為著名，皆為貪婪演算法

• Greedy method，特性是每個階段都能得到最好的結果，最後的結果也是最好的

Kruskal's Algorithm

依次找尋圖形中加權值最小的邊加入spanning tree，嘗試連結圖的N個頂點，但不使用會造成圖形成環路的邊，直到產生N-1個邊。

• 又到了以圖片為例子的時間了:
  
  1. 先找出圖中權重最小的邊是1，所以邊EG連上
     
  2. 圖中權重次小的邊是2，所以邊DE連上
     
  3. 圖中剩下的邊裡面權重最小是3，所以邊AD連上
     
  4. 圖中剩下的邊裡面權重最小是4，所以邊CE連上
     
  5. 找出圖中剩下的邊裡面權重最小是6，圖中藍邊AC和綠邊BC權重都是6
     
  6. 若選擇邊AC會造成環路，所以選擇BC
     
  7. 圖中剩下的邊裡面權重最小是8，，但會造成環路，所以AB邊不連接
     
  8. 圖中剩下的邊裡面權重最小是9，，但會造成環路，所以CG邊不連接
     
  9. 最後找到的Minimum spanning tree
     

明天介紹Prim's Algorithm。

參考

細談資料結構 第六版
ISBN 978-986-312-014-8