kruskal算法
1.概覽
kruskal算法是一種用來尋找最小生成樹的算法，由joseph
kruskal在1956年發表。用來解決同樣問題的還有prim算法和boruvka算法等。三種算法都是貪婪算法的應用。和boruvka算法不同的地方是，kruskal算法在圖中存在相同權值的邊時也有效。
2.算法簡單描述
1).記graph中有v個頂點，e個邊
2).建立圖graphnew，graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).将原圖graph中所有e個邊按權值從小到大排序
4).循環：從權值最小的邊開始周遊每條邊
直至圖graph中所有的節點都在同一個連通分量中
if 這條邊連接配接的兩個節點于圖graphnew中不在同一個連通分量中
添加這條邊到圖graphnew中
圖例描述：
首先第一步，我們有一張圖graph，有若幹點和邊
将所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這裡再次展現了貪心算法的思想。資源排序，對局部最優的資源進行選擇，排序完成後，我們率先選擇了邊ad。這樣我們的圖就變成了下圖
在剩下的圖中尋找。我們找到了ce。這裡邊的權重也是5
依次類推我們找到了6,7,7，即df，ab，be。
下面繼續選擇，
bc或者ef盡管現在長度為8的邊是最小的未選擇的邊。但是現在他們已經連通了（對于bc可以通過ce,eb來連接配接，類似的ef可以通過eb,ba,ad,df來接連）。是以不需要選擇他們。類似的bd也已經連通了（這裡上圖的連通線用紅色表示了）。
最後就剩下eg和fg了。當然我們選擇了eg。最後成功的圖就是下圖：
3.簡單證明kruskal算法
對圖的頂點數n做歸納，證明kruskal算法對任意n階圖适用。
歸納基礎：
n=1，顯然能夠找到最小生成樹。
歸納過程：
假設kruskal算法對n≤k階圖适用，那麼，在k+1階圖g中，我們把最短邊的兩個端點a和b做一個合并操作，即把u與v合為一個點v‘，把原來接在u和v的邊都接到v‘上去，這樣就能夠得到一個k階圖g‘(u,v的合并是k+1少一條邊)，g‘最小生成樹t‘可以用kruskal算法得到。
我們證明t‘+{<u,v>}是g的最小生成樹。
用反證法，如果t‘+{<u,v>}不是最小生成樹，最小生成樹是t，即w(t)<w(t‘+{<u,v>})。顯然t應該包含<u,v>，否則，可以用<u,v>加入到t中，形成一個環，删除環上原有的任意一條邊，形成一棵更小權值的生成樹。而t-{<u,v>}，是g‘的生成樹。是以w(t-{<u,v>})<=w(t‘)，也就是w(t)<=w(t‘)+w(<u,v>)=w(t‘+{<u,v>})，産生了沖突。于是假設不成立，t‘+{<u,v>}是g的最小生成樹，kruskal算法對k+1階圖也适用。
由數學歸納法，kruskal算法得證。
view
code
轉：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html