> For the complete documentation index, see [llms.txt](https://garychang.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garychang.gitbook.io/data-structure/4-graph/4.3-spanning-tree/4.3.1-kruskals-algorithm.md).
# 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