關于最小生成樹，我曾經了解過，然後上離散數學後又了解了一遍，是以就向想一下這個部落格；主要是了解和證明；
.首先我們什麼提出最小生成樹概念：
設無向連通帶權圖G=<V,E,W>,T是G的一顆生成樹，T的各邊權之和稱為T的權，記作W（T）。G的所有生成樹中權最小的生成樹稱為G的最小生成樹。
求最小生成樹已經有許多種方法，這裡介紹的是避圈法（Kruskal）；
怎樣找出最小生成樹：
設n階無向連通圖帶權圖G=<V,E,W>有m條邊，不妨設G中沒有環（否則，可以将所有的環先删去），将m條邊按權從小到大順序排序，設e1,e2,e3…em;
取e1在T中，然後依次檢查e1,e2,e3…em。若ej（j>=2）與已在T中的邊不能構成回路，則取ej在T中，否則棄去ej。
算法停止時得到的T為G的最小生成樹；
下面這個第一張圖檔是G無向連通圖；第二張圖檔是T，即G的最小生成樹；
了解了，那麼我們就來證明一下這個算法的正确性；
1.首先，假設我們已經對所有邊進行了排序，并且目前周遊到的邊是連接配接點1和點3的邊。
2.因為這條邊是最小的邊，而點1和點3在最小生成樹中一定會直接或間接的相連，是以任何從點1到點3的路徑都不小于這條邊。如圖，如果不走這條邊就走1→2→3 或者1->4->3（而如果這樣走顯然會使得1→3的距離過大，而我們目前隻讨論1→3的最優選項）。或者，我們可以假設一種情況：點1和點3之間有兩條權值為0.25的邊，間接的連接配接了點1和點3，那麼這條路徑顯然比目前權值為1的邊的權值小。但是我們是從小到大周遊邊的，是以如果出現了這種情況，那麼由于比權值為1的這條邊小，那麼他們必定已經被周遊。
由于那條路徑已經被周遊過，那麼這時候點1和點3就處于一個并查集了，也就是說我們不會再選擇邊權為3的這條邊了。
3.是以我們可以證明出一個結論：圖中權值最小的這條邊必然要被選擇。
4.假設我們已經選擇了直接連接配接點1和點3的這條邊，那麼我們就可以對點1和點3進行縮點，由于最小生成樹的性質（隻要有路徑連接配接兩個任意結點即可），縮點對建圖沒有任何影響。
5.重複以上操作，直到邊的數量等于點的數量減一（一個圖的最小生成樹的邊的數量必定等于這個圖的點的數量減一）即可得出最小生成樹。
接下來就是上代碼了：
由于時間關系先寫到這，後再填坑；
這裡一道是關于避圈法（Kruskal算法）的題解；
請點這裡