---
# System prepended metadata

title: Kruskal’s algorithm

---

# Kruskal’s algorithm

Kruskal演算法的方式是從所有邊中，反覆選擇最短的邊，它的步驟是：

1.  將所有的邊依照權重由小到大排序。
2.  從最小開始，選擇不會形成環的邊，直到連接所有節點。

如下圖，先將邊排序，依序選擇，其中邊be即是因為會形成環所以不選。

![](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/MST_kruskal_en.gif/383px-MST_kruskal_en.gif)

## 參考資料

[3.5 Prims and Kruskal algorithms - Greedy Method](https://www.youtube.com/watch?v=4ZlRH0eK-qQ)