克魯斯卡爾算法(Kruskal's algorithm)是兩個經典的最小生成樹算法的較為簡單理解的一個。

    這里面充分體現了貪心算法的精髓。

   大致的流程可以用一個圖來表示。這里的圖的選擇借用了Wikipedia上的那個。非常清晰且直觀。

　　首先第一步，我們有一張圖，有若干點和邊

　　如下圖所示：

　　

.

　　.

　　.

　　.

　　.

　　.

　　第一步我們要做的事情就是將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。

       這里再次體現了貪心算法的思想。資源排序，對局部最優的資源進行選擇。

　　排序完成后，我們率先選擇了邊AD。 這樣我們的圖就變成了

　　

.

　　.

　　.

　　.

　　.

　　.

　　第二步，在剩下的變中尋找。我們找到了CE。這里邊的權重也是5

　　

.

　　.

　　.

　　.

　　.

　　.

　　依次類推我們找到了6,7,7。完成之后，圖變成了這個樣子。

　　

.

　　.

　　.

　　.

　　.

　　.

　　下一步就是關鍵了。下面選擇那條邊呢？ BC或者EF嗎？都不是，盡管現在長度為8的邊是最小的未選擇的邊。

       但是現在他們已經連通了（對于BC可以通過CE,EB來連接，類似的EF可以通過EB, BA, AD, DF來接連）。

       所以我們不需要選擇他們。類似的BD也已經連通了（這里上圖的連通線用紅色表示了）。

　　最后就剩下EG和FG了。當然我們選擇了EG。 最后成功的圖就是下圖：

　　

.

　　.

　　.

　　.

　　.

　　.

　　到這里所有的邊點都已經連通了，一個最小生成樹構建完成。

      

      當然，在處理最后一步的時候就要用到并查集了。