和Prim算法求圖的最小生成樹一樣，Kruscal算法求最小生成樹也用到了貪心的思想，隻不過前者是貪心地選擇點，後者是貪心地選擇邊。而且在算法的實作中，我們還用用到了并查集（也稱不相交集的）Union /Find 算法來判斷兩個節點連通後會不會形成一個環。該算法的思想很簡單：将圖的所有邊按從小到大順序排序，每次都選取權值最小的邊加入最小生成樹，如果該邊的加入會使生成樹形成一個環，則跳過該邊。
這裡引入并查集的概念，可以使問題變得簡單化。并查集就是利用一個數組sets，如果sets[a]=b，那麼我們說a和b在一個生成樹（集合）中，且a的雙親是b，如果sets[a]=a,那麼我們說a是一個生成樹的根。一個圖的最小生成樹在還沒有完全生成前，可能存在多個互不連通的生成樹，他們是不相交的集合，我們需要把這些不同的生成樹連通起來。
于是，通過定義一個findroot函數，我們可以找到某頂點的雙親，然後找到該頂點的雙親的雙親，最終找到頂點所在最小生成樹的根，例如：如果我們知道sets[a]=b,sets[b]=c,sets[c]=c，那我們可以說a、b、c在同一棵生成樹(集合)裡，且所在最小生成樹的根為c。假設另一個不相交的生成樹的根為d，如果我們令sets[c]=d,則将這兩個生成樹合并為了一個大的生成樹，其根為d。
1.建立一個9條邊，6個頂點的帶權無向連通圖。
初始狀态的并查集如下：
2.将圖所有邊按權值進行排序。選擇權值最小的一條邊的兩個鄰點。為了避免混亂，統一約定該邊右邊的鄰點加入左邊的鄰點的并查集中，在圖中表示為2頂點挂在1頂點下面。
3.就這樣，按照權值從小到大不斷周遊所有邊，都統一把邊的大序号的鄰點加入小序号的鄰點所在的生成樹中，3頂點挂在2頂點下面，4頂點挂在3頂點下面，5頂點挂在4頂點下面，6頂點挂在2頂點的下面，最終最小生成樹不斷長大，且最後所有頂點本質上都挂在1頂點下面，即最小生成樹的根為1頂點。
4.最好還剩4條邊沒有周遊。但我們發現，這4條邊的兩個鄰點都在同一個生成樹中了，即他們findroot的結果都是1。如果我們把任意一條邊的兩個鄰點連接配接起來，都會形成一個環，這是不允許的。故最小生成樹的生成就此結束。
1.引入頭檔案，和之前所講的的其他圖論算法不同的是，這裡單獨定義一個表示圖的邊的類，用u，v記錄邊的鄰接點，w記錄邊的權值。
2.定義表示圖的類
3.這裡自定義一個排序比較函數，後面給儲存邊的容器排序時會用到。
4.Graph類的構造函數以及析構函數
5.Kruscal算法的實作。
6.尋根函數的實作
7.對頂點按照權值排序函數的實作
8.測試部分。定義一個6個頂點9條邊的圖，調用接口求該圖的最小生成樹
控制台輸出結果：
數學是符号的藝術，音樂是上界的語言。