首頁 >Java >java教程 >關於最小生成樹的實例詳解

關於最小生成樹的實例詳解

零下一度
零下一度原創
2017-06-25 13:30:283460瀏覽

最小生成樹-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來描述所得到的最小生成樹。

 

下面對演算法的圖例描述

##A, D演算法繼續重複上面的步驟。距離CB, E, GA, D, F 
圖例 說明 不可選 ##可選 #已選(Vnew

此為原始的加權連通圖。每條邊一側的數字代表其權值。 - - -

頂點D任意選為起始點。頂點ABEF透過單一邊與D連結。 A是距離D最近的頂點,因此將A及對應邊AD以高亮表示。 C, G A, B, E, F D
 

#下一個頂點為距離DA最近的頂點。 BD為9,距A為7,E為15,F為6。因此,FDA最近,因此將頂點F與對應邊DF以高亮表示。 C, G B, E, F
A為7的頂點B以高亮表示。

#

在目前情況下,可以在CEG間進行選擇。 CB為8,EB為7,GF為11。 E最近,因此將頂點E與對應邊BE高亮表示。 C, E, G A, D, F, B
 

#這裡,可選取的頂點只有CGCE為5,GE為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)。新建圖Graph

new,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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn