克魯斯卡爾算法

克魯斯卡爾（Kruskal）算法從另一途徑求網的最小生成樹。其基本思想是：假設連通網G=（V，E），令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖T=（V，{}），概述圖中每個頂點自成一個連通分量。在E中選擇代價最小的邊，若該邊依附的頂點分別在T中不同的連通分量上，則將此邊加入到T中；否則，捨去此邊而選擇下一條代價最小的邊。依此類推，直至T中所有頂點構成一個連通分量為止 ^[2]  。

對於圖7.18（a）所示的網，按照克魯斯卡爾方法構造最小生成樹的過程如圖7.20所示： ^[3] 

圖7.20中按權值由小到大的順序排列的編輯是：（各邊由起點序號，終點序號，權值表示） ^[3] 

1.(4,6,30) 2.(2,5,40) 3.(4,7,42) 4.(3,7,45)

5.(1,2,50) 6.(4,5,50) 7.(3,4,52) 8.(1,3,60)

9.(2,4,65) 10.(5, 6, 70)

克魯斯卡爾算法思想設計克魯斯卡爾算法函數主要包括兩個部分：首先是帶權圖G中e條邊的權值的排序；其次是判斷新選取的邊的兩個頂點是否屬於同一個連通分量。對帶權圖G中e條邊的權值的排序方法可以有很多種，各自的時間複雜度均不相同，對e條邊的權值排序算法時間複雜度較好的算法有快速排序法、堆排序法等，這些排序算法的時間複雜度均可以達到O（elge）。判斷新選取的邊的兩個頂點是否屬於同一個連通分量的問題是一個在最多有n個頂點的生成樹中遍歷尋找新選取的邊的兩個頂點是否存在的問題，此算法的時間複雜度最壞情況下為O（n） ^[4]  。

克魯斯卡爾算法的時間複雜度主要由排序方法決定，而克魯斯卡爾算法的排序方法只與網中邊的條數有關，而與網中頂點的個數無關，當使用時間複雜度為O（elog₂e）的排序方法時，克魯斯卡爾算法的時間複雜度即為O（log₂e），因此當網的頂點個數較多、而邊的條數較少時，使用克魯斯卡爾算法構造最小生成樹效果較好 ^[5-6]  。

無向連通網的最小生成樹首先是一棵生成樹，即它應該是一個使網中所有頂點相連通而所需邊的條數為最小的子網絡，且其代價和在所有生成樹中為最小。因此，可以從網的連通性角度來觀察Kruskal算法 ^[7]  。

初始時，最小生成樹就是網中所有頂點的集合，它們之間沒有任何一條邊連接，即它們自成一個連通分量。而Kruskal算法的執行過程其實就是一個選取網中權值為最小的邊的過程，即將兩個小的連通分量連接為較大的連通分量，直至所有頂點都在一個連通分量中為止。每當選取網中的一條邊時總會出現以下兩種情況之一： ^[7] 

①該邊所依附的兩個頂點分屬於不同的連通分量。這時，該邊可以作為最小生成樹的一條邊，因為兩個不同的連通分量通過這條邊的連接而相連通，成為了一個連通分量 ^[7]  。

②該邊所依附的兩個頂點屬於同一個連通分量。如果選取這條邊作為最小生成樹的一條邊，則必將構成環。因為連通分量中任意兩個頂點間都有路徑相通，一旦再加入一條邊，該邊所依附的兩個頂點之間就有了兩條路徑，即構成了環。故屬於這種情況的邊即使其權值小也應該捨棄 ^[7]  。