除了Prim’s algorithm可以找出MST(Minimum Spanning Tree)外，還有一個常見的演算法叫做Kruskal’a algorithm。

Kruskal’a algorithm找MST的方法相當直觀暴力，就是先列出所有的edge，並按照edge的weight由小排到大，然後一個一個檢視若納入MST時會不會有cycle，有cycle就跳過，看看下一個edge會不會造成cyclic，當找到所有的點都相連時就結束了。

我們把上述的內容整理一下，其實就是3個步驟：

1. 找出weight最小的edge
2. 檢查有沒有cycle，沒cycle就加入MST，有cycle就略過
3. 當MST包含到所有節點就結束

實際上應該如何做到上述的步驟？其實在先前的章節都有相對應的工具可以應用！

步驟1就是先把所有的edge加進PQ(Priority Queue)，之後就可以拿出weight最小的edge了；

而步驟2要如何檢查有沒有cycle呢？這時候就可以應用WQU(Weighted Quick Union)，檢查edge的兩個節點有沒有isConnected()，沒有的話就union()；

步驟3就只要判斷MST中是不是已經擁有V-1個edge就行了。

下面實際來看個範例：

從Fringe拿出0-2，判斷isConnected(0, 2)：

isConnected(0, 2)是false，故把0-2加到WQU和MST：

然後依此類推從Fringe拿出下一個edge 2-4：

isConnected(2, 4)是false，所以加入WQU和MST：

以此類推，我們來看看當遇到cycle時：

isConnected(1, 4)為true，所以不加入WQU跟MST，進行下一個Fringe~

直到最後MST.size() = 6，V = 7，剛好V - 1 = MST.size()，就此完成～

為什麼Kruskal’s algorithm可以work呢？

來分析看看，我們把已經加到MST的edge標註為黑色，當我們在判斷0-2時，我們把這個cut中與MST已經和節點0相連的點視為一邊並標註為灰色，另一邊標註為白色；

首先，不會有crossing edge會是黑色edge，因為我們在加入MST時（標注edge為黑色時），有cycle是不允許的；

再來，因為我們是從weight小到大來判斷，所以當前的0-2就會是weight最小的crossing edge了。

我們來看看Kruskal的runtime：

以下為當前有關於graph的演算法runtime總結：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License