檢視克魯斯克爾演算法的原始碼

'''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 if'''u 和 v 無仝一欉樹仔七'''then'''F  :=F ∪ { ( u , v ) }
八將 u 和 v 所在的子樹合做伙
` ` `

==參考源程式==

===C + + 實現===

以下代碼基於路徑壓縮佮揤秩合併的併查集，時間複雜度 $ O ( | E | \ alpha ( | V | ) ) $。

==參考文獻==

[[分類: 待校正]]