克魯斯克爾演算法
Kruskal 演算法是一種用來走揣上小生成樹仔的演算法，由 Joseph Kruskal 佇咧一九五六年發表。用來解決仝款問題的猶閣有 Prim 演算法佮 Boruvka 演算法等。三種演算法攏是貪婪演算法的應用。和 Boruvka 演算法無仝的所在是，Kruskal 演算法佇圖中存在仝款權值的邊仔的時陣嘛有效。
撇步
一 . 新建圖 $ G $，$ G $ 中擁有原圖中相仝的節點，伊無邊二 . 共原圖中所有的那揤權值自細漢到大漢排序三 . 對權值上細漢的邊仔開始，若這條邊連接的兩个節點於圖 $ G $ 著無仝一个連通的量內底，則添加這條邊到圖 $ G $ 中四 . 重複三，直至圖 $ G $ 中所有的點仝款攏佇咧連通分開中
證明
一 . 這款的撇步保證矣選取的逐條邊攏是橋，所以圖 $ G $ 鹿仔成一个樹。 二 . 為啥物這一定是上小生仔唅？關鍵猶閣是行三中對邊的選取。演算法中攏總選取矣 $ n 影一 $ 條邊，逐條邊咧選取的彼當陣，攏是連接兩个無仝的連通分量的權值上細的邊仔三 . 欲證明這條邊一定屬於上小生成樹，會當用反證法：若這條邊無佇細漢的樹仔內底，伊連接的兩个連通分開終猶是愛連起來的，通過其他的連法，遮另外一種連法佮這條邊仔一定構成矣環，若環中一定有一條權值大過這條邊的邊仔，用這條邊仔共換掉，猶原保持連通，但是總權值減細矣。也就是講，若無選這條邊，落尾手構成的成樹的總權值一定袂是上細的。
時間複雜度
通過使用路徑壓縮的併查集，平均時間複雜度做 $ O ( | E | \ log | V | ) $，其中 $ E $ 和 $ V $ 分別是圖的邊集佮點集。
此外，若同時使用路徑壓縮佮揤秩合併，時間複雜度會當最佳化甲 $ O ( | E | \ alpha ( | V | ) ) $，其中 $ \ alpha $ 表示反阿克曼函數。
範例
虛擬碼
` ` ` KRUSKAL-FUNCTION ( G , w ) 一 F :=空集合二for each圖 G 中的頂點 v 三do將 v 加入去森林 F 四所有的邊 ( u , v ) ∈ E 依權重 w 遞增排序五for each邊 ( u , v ) ∈ E 六do ifu 和 v 無仝一欉樹仔七thenF :=F ∪ { ( u , v ) } 八將 u 和 v 所在的子樹合做伙 ` ` `
參考源程式
C + + 實現
以下代碼基於路徑壓縮佮揤秩合併的併查集，時間複雜度 $ O ( | E | \ alpha ( | V | ) ) $。