克魯斯卡爾算法是一種用來尋找最小生成樹的算法（用來求加權連通圖的最小生成樹的算法）。在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構成回路，則放棄，選取次小邊。1、將圖的所有連接線去掉，只剩頂點，

2、?從圖的邊集數(shù)組中找到權值最小的邊，將邊的兩個頂點連接起來，3、?繼續(xù)尋找權值最小的邊，將兩個頂點之間連接起來，如果選擇的邊使得最小生成樹出現(xiàn)了環(huán)路，則放棄該邊，選擇權值次小的邊4、?直到所有的頂點都被連接在一起并且沒有環(huán)路，最小生成樹就生成了。

基本思想

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

過程

對于圖7.18（a）所示的網(wǎng)，按照克魯斯卡爾方法構造最小生成樹的過程如圖7.20所示：

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

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

圖7.18（a）

圖7.18（a）

9. - 2,4,65?10. - 5,?6,?70

包含

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

復雜度

克魯斯卡爾算法的時間復雜度主要由排序方法決定，而克魯斯卡爾算法的排序方法只與網(wǎng)中邊的條數(shù)有關，而與網(wǎng)中頂點的個數(shù)無關，當使用時間復雜度為O（elog2e）的排序方法時，克魯斯卡爾算法的時間復雜度即為O（log2e），因此當網(wǎng)的頂點個數(shù)較多、而邊的條數(shù)較少時，使用克魯斯卡爾算法構造最小生成樹效果較好。

觀察Kruskal算法

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

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

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

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