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

最小生成樹-Prim演算法和Kruskal演算法

圖的生成樹是它的一棵含有所有頂點的無環連通子圖，一棵加權圖的最小生成樹是它的一棵權值最小的生成樹。

Prim演算法

#演算法簡單描述

1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E;

2).初始化：V_new = {x}，其中x為集合V中的任一節點（起始點），E_new = {},為空;

3).重複下列操作，直到V_new = V：

a.在集合E中選取權值最小的邊，其中u為集合V _new中的元素，而v不在V_new集合當中，且v∈V（如果存在有多個滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

b.將v加入集合V_new中，將邊加入集合E_new中；

4).輸出：使用集合V_new和E_new來描述所得到的最小生成樹。

 

下面對演算法的圖例描述

##A, D演算法繼續重複上面的步驟。距離CB, E, GA, D, F 

圖例	說明	不可選	##可選	#已選（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為7的頂點B以高亮表示。
#	在目前情況下，可以在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)。新建圖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中文網其他相關文章！