最小生成樹英文是Minimum Spanning Tree，對于最小生成樹大家應(yīng)該都不陌生，當(dāng)然還有最大生成樹，首先就簡單總結(jié)一下算法里的生成樹。

一、什么是生成樹？

Spanning有跨越的意思，生成樹一般來說每個節(jié)點(diǎn)都能訪問到別的節(jié)點(diǎn)，是一個連通樹。所以，一般考慮無向圖里去造生成樹。生成樹又分最小和最大兩種，其中最小生成樹應(yīng)用比較多?？偨Y(jié)一下生成樹的定義：

1. 首先它得是一個樹的結(jié)構(gòu)

2. 所有的節(jié)點(diǎn)都能互相訪問

3. 要么最小要么最大（廢話）

如下圖所示，加粗的黑邊就是最小生成樹。

特性

生成樹有兩個看起來很廢話的特性 Cycle Property 和 Cut Property，這里以最小生成樹為主來說明。

Cycle Property

如果在一個環(huán)里，其中某條邊 e 是這里面的權(quán)重最大的邊，那么這條邊一定不在最小生成樹里。

舉個例子，上圖我們看到其中一個環(huán) 0 -> 1 -> 7 -> 0，我們發(fā)現(xiàn)邊 1 -> 7 是這里面權(quán)重最大的，那么就一定不會在這張圖的最小生成樹里。

Cut Property

再來看看 Cut Property，如果你把圖里的節(jié)點(diǎn)分成兩堆，里面最權(quán)重最小的邊是一定會在這張圖的最小生成樹里的。

二、最小生成樹

一個有 n 個結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n個結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普里姆）算法求出。簡單明了就是求最小的連通圖。

舉個例子：

這幅圖的極小連通圖為

或者

就是從一個點(diǎn)能到達(dá)圖的任意一點(diǎn)，且花費(fèi)的代價最?。ㄋ羞叺臋?quán)值最?。?/p>

三、代碼描述

（一）Prim算法

1. 概覽

普里姆算法（Prim算法），圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹。意即由此算法搜索到的邊子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)（英語：Vertex (graph theory)），且其所有邊的權(quán)值之和亦為最小。該算法于1930年由捷克數(shù)學(xué)家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發(fā)現(xiàn)；并在1957年由美國計算機(jī)科學(xué)家羅伯特·普里姆（英語：Robert C. Prim）獨(dú)立發(fā)現(xiàn)；1959年，艾茲格·迪科斯徹再次發(fā)現(xiàn)了該算法。因此，在某些場合，普里姆算法又被稱為DJP算法、亞爾尼克算法或普里姆－亞爾尼克算法。

2. 算法簡單描述

（1）輸入：一個加權(quán)連通圖，其中頂點(diǎn)集合為V，邊集合為E；

（2）初始化：Vnew = {x}，其中x為集合V中的任一節(jié)點(diǎn)（起始點(diǎn)），Enew = {},為空；

（3）重復(fù)下列操作，直到Vnew = V：

a. 在集合E中選取權(quán)值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當(dāng)中，并且v∈V（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；

b. 將v加入集合Vnew中，將<u, v>邊加入集合Enew中；

（4）輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。

3.下面對算法的圖例描述

圖例	說明	不可選	可選	已選（Vnew）
	為原始的加權(quán)連通圖。每條邊一側(cè)的數(shù)字代表其權(quán)值。	-	-	-
	頂點(diǎn)D被任意選為起始點(diǎn)。頂點(diǎn)A、B、E和F通過單條邊與D相連。A是距離D最近的頂點(diǎn)，因此將A及對應(yīng)邊AD以高亮表示。	C, G	A, B, E, F	D
	下一個頂點(diǎn)為距離D或A最近的頂點(diǎn)。B距D為9，距A為7，E為15，F(xiàn)為6。因此，F(xiàn)距D或A最近，因此將頂點(diǎn)F與相應(yīng)邊DF以高亮表示。	C, G	B, E, F	A, D
	算法繼續(xù)重復(fù)上面的步驟。距離A為7的頂點(diǎn)B被高亮表示。	C	B, E, G	A, D, F
	在當(dāng)前情況下，可以在C、E與G間進(jìn)行選擇。C距B為8，E距B為7，G距F為11。E最近，因此將頂點(diǎn)E與相應(yīng)邊BE高亮表示。	無	C, E, G	A, D, F, B
	這里，可供選擇的頂點(diǎn)只有C和G。C距E為5，G距E為9，故選取C，并與邊EC一同高亮表示。	無	C, G	A, D, F, B, E
	頂點(diǎn)G是唯一剩下的頂點(diǎn)，它距F為11，距E為9，E最近，故高亮表示G及相應(yīng)邊EG。	無	G	A, D, F, B, E, C
	現(xiàn)在，所有頂點(diǎn)均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權(quán)值之和為39。	無	無	A, D, F, B, E, C, G

3. 簡單證明prim算法

反證法：假設(shè)prim生成的不是最小生成樹

（1）設(shè)prim生成的樹為G0；

（2）假設(shè)存在Gmin使得cost(Gmin)<cost(G0)   則在Gmin中存在<u,v>不屬于G0；

（3）將<u,v>加入G0中可得一個環(huán)，且<u,v>不是該環(huán)的最長邊(這是因?yàn)?lt;u,v>∈Gmin)；

（4）這與prim每次生成最短邊矛盾；

（5）故假設(shè)不成立，命題得證。

（二）Kruskal算法

1. 概覽

Kruskal算法是一種用來尋找最小生成樹的算法，由Joseph Kruskal在1956年發(fā)表。用來解決同樣問題的還有Prim算法和Boruvka算法等。三種算法都是貪婪算法的應(yīng)用。和Boruvka算法不同的地方是，Kruskal算法在圖中存在相同權(quán)值的邊時也有效。

2. 算法簡單描述

（1）記Graph中有v個頂點(diǎn)，e個邊

（2）新建圖Graphnew，Graphnew中擁有原圖中相同的e個頂點(diǎn)，但沒有邊

（3）將原圖Graph中所有e個邊按權(quán)值從小到大排序

（4）循環(huán)：從權(quán)值最小的邊開始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個連通分量中 if 這條邊連接的兩個節(jié)點(diǎn)于圖Graphnew中不在同一個連通分量中，添加這條邊到圖Graphnew中

圖例描述：

首先第一步，我們有一張圖Graph，有若干點(diǎn)和邊。

將所有的邊的長度排序，用排序的結(jié)果作為我們選擇邊的依據(jù)。這里再次體現(xiàn)了貪心算法的思想。資源排序，對局部最優(yōu)的資源進(jìn)行選擇，排序完成后，我們率先選擇了邊AD。這樣我們的圖就變成了上圖。

在剩下的變中尋找。我們找到了CE。這里邊的權(quán)重也是5

依次類推我們找到了6,7,7，即DF，AB，BE。

下面繼續(xù)選擇，BC或者EF盡管現(xiàn)在長度為8的邊是最小的未選擇的邊。但是現(xiàn)在他們已經(jīng)連通了（對于BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以不需要選擇他們。類似的BD也已經(jīng)連通了（這里上圖的連通線用紅色表示了）。

最后就剩下EG和FG了。當(dāng)然我們選擇了EG。