最小生成樹-Prim演算法和Kruskal演算法
圖的生成樹是它的一棵含有所有頂點的無環連通子圖,一棵加權圖的最小生成樹是它的一棵權值最小的生成樹。
Prim演算法
#演算法簡單描述
1).輸入:一個加權連通圖,其中頂點集合為V,邊集合為E;
2).初始化:Vnew = {x},其中x為集合V中的任一節點(起始點),Enew = {},為空;
3).重複下列操作,直到Vnew = V:
a.在集合E中選取權值最小的邊,其中u為集合V new中的元素,而v不在Vnew集合當中,且v∈V(如果存在有多個滿足前述條件即具有相同權值的邊,則可任意選取其中之一);
b.將v加入集合Vnew中,將邊加入集合Enew中;
4).輸出:使用集合Vnew和Enew來描述所得到的最小生成樹。
下面對演算法的圖例描述
圖例 | 說明 | 不可選 | ##可選 | #已選(Vnew) |
---|---|---|---|---|
#
|
此為原始的加權連通圖。每條邊一側的數字代表其權值。 | - | - | - |
頂點D任意選為起始點。頂點A、B、E和F透過單一邊與D連結。 A是距離D最近的頂點,因此將A及對應邊AD以高亮表示。 | C, G | A, B, E, F | D | |
|
#下一個頂點為距離D或A最近的頂點。 B距D為9,距A為7,E為15,F為6。因此,F距D或A最近,因此將頂點F與對應邊DF以高亮表示。 | C, G | B, E, F | ##A, D|
演算法繼續重複上面的步驟。距離 | A為7的頂點B以高亮表示。 | CB, E, G | A, D, F | |
# |
在目前情況下,可以在C、E與G間進行選擇。 C距B為8,E距B為7,G距F為11。 E最近,因此將頂點E與對應邊BE高亮表示。 | 無 | C, E, G | A, D, F, B |
|
#這裡,可選取的頂點只有C和G。 C距E為5,G距E為9,故選取C,並與邊EC一同高亮表示。 | 無 | C, G | A, D, F, B, E |
#頂點G是唯一剩下的頂點,它距F為11,距E為9,E最近,故高亮表示G及對應邊EG。 | 無 | G | #A, D, F, B, E, C | |
#現在,所有頂點都已被選取,圖中綠色部分即為連通圖的最小生成樹。在此例中,最小生成樹的權值總和為39。 | 無 | #無 | #A, D, F, B, E, C, G |
演算法實作可參考《演算法》第四版,或清華出版社《資料結構—java語言實作》(實作方法更清晰簡單)
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
中不在同一個連通分量中##中
圖例說明:
首先第一步,我們有一張圖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。 ######### ###############演算法實作可參考《演算法》第四版程式碼。 ##########以上是關於最小生成樹的實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!