本文同步於個人Blog → InformisTry - HankLee

前言

昨天講了Prim's Algorithm，今天要講另一個Greedy Algorithm - Kruskal's Algorithm

Kruskal's Algorithm是什麼？

Kruskal's Algorithm跟Prim's Algorithm的做法其實有點類似，但是Prim's Algorithm在選值的過程中，會依據值的大小改變排隊順序，而Kruskal's Algorithm選擇的條件則是針對整個Graph來判斷值的大小，然後從小的路線開始選，而且還有一個條件：選擇的路線不能讓節點形成環狀。

Kruskal's Algorithm的流程

Kruskal's Algorithm基本的流程如下：

1. 先將所有路徑的資訊都整理好，並從小至大排列。
2. 從整個Graph中挑選出最小值的『路徑』，且這個路徑不會讓已經選中的其他路徑形成環狀
3. 反覆執行第二步，直到記錄下來的路徑數量為節點數量減1。（如果五個節點，需要四個路徑才能把這五個節點都連接起來）

看看上面的範例，首先先將所有的路徑都條列出來，然後再根據其值一一選擇，一旦當所選擇的路徑與其他已選擇的路徑形成環狀，就會跳過當前選擇的路徑，直到最後選擇的路徑數為節點數減1（範例中共有7個節點，執行完畢後，所選擇的路徑數共有6條）。

理論上，Kruskal's Algorithm看起來比Prim's Algorithm簡單，但是實際上卻不然；Kruskal's Algorithm比較難以實現是因為最麻煩的步驟是要去確認當前所選擇的路徑是否會形成環狀，從圖片上來看會覺得很簡單，但程式看不到，所以這個是實作上最麻煩的步驟。

小結

Kruskal's Algorithm再決定路徑時，除了依照賦予在當前路徑的值的大小之外，當前所選擇的路徑還不能與其他已選擇的路徑形成環狀，而這也是程式實作上最為麻煩的部分。

預告

明天我們將會再介紹另外一種解決同一個問題的演算法 - Dijkstra's Algorithm。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin