基本介紹
- 中文名：克魯斯克爾演算法
- 外文名：Kruskal's algorithm
- 學科：數學、計算機科學
- 套用：數據結構
簡介,算法步驟,證明,時間複雜度,算法程式,
簡介
Kruskal算法是一種用來查找最小生成樹的算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪心算法的套用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權值的邊時也有效。
算法步驟
- 新建圖G，G中擁有原圖中相同的節點，但沒有邊；
- 將原圖中所有的邊按權值從小到大排序；
- 從權值最小的邊開始，如果這條邊連線的兩個節點於圖G中不在同一個連通分量中，則添加這條邊到圖G中；
- 重複3，直至圖G中所有的節點都在同一個連通分量中。
算法圖解證明
- 這樣的步驟保證了選取的每條邊都是橋，因此圖G構成一個樹；
- 為什麼這一定是最小生成樹呢？關鍵還是步驟3中對邊的選取。算法中總共選取了n-1條邊，每條邊在選取的當時，都是連線兩個不同的連通分量的權值最小的邊；
- 要證明這條邊一定屬於最小生成樹，可以用反證法：如果這條邊不在最小生成樹中，它連線的兩個連通分量最終還是要連起來的，通過其他的連法，那么另一種連法與這條邊一定構成了環，而環中一定有一條權值大於這條邊的邊，用這條邊將其替換掉，圖仍舊保持連通，但總權值減小了。也就是說，如果不選取這條邊，最後構成的生成樹的總權值一定不會是最小的。
時間複雜度
平均時間複雜度為
，其中E和V分別是圖的邊集和點集。
算法程式
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 所在的子樹合併
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 所在的子樹合併
