最小生成樹：一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。

最小生成樹可以用kruskal（克魯斯卡爾）算法或PRim（普里姆）算法求出。

例如：要在n個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是要使這 n 個(gè)城市的任意兩個(gè)之間都可以通信，但鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之間鋪設(shè)光纜的費(fèi)用不同，因此另一個(gè)目標(biāo)是要使鋪設(shè)光纜的總費(fèi)用最低。這就需要找到帶權(quán)的最小生成樹。

Prim算法簡(jiǎn)述

圖例描述:

圖例	說明	不可選	可選	已選（Vnew）
	此為原始的加權(quán)連通圖。每條邊一側(cè)的數(shù)字代表其權(quán)值。	-	-	-
	頂點(diǎn)D被任意選為起始點(diǎn)。頂點(diǎn)A、B、E和F通過單條邊與D相連。A是距離D最近的頂點(diǎn)，因此將A及對(duì)應(yīng)邊AD以高亮表示。	C, G	A, B, E, F	D
	下一個(gè)頂點(diǎn)為距離D或A最近的頂點(diǎn)。B距D為9，距A為7，E為15，F為6。因此，F距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

算法簡(jiǎn)單描述

1).記Graph中有v個(gè)頂點(diǎn)，e個(gè)邊

2).新建圖Graph_new，Graph_new中擁有原圖中相同的e個(gè)頂點(diǎn)，但沒有邊

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

4).循環(huán)：從權(quán)值最小的邊開始遍歷每條邊 直至圖Graph中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中

                if （這條邊連接的兩個(gè)節(jié)點(diǎn)于圖Graph_new中不在同一個(gè)連通分量中）

                添加這條邊到圖Graph_new中

圖例描述：

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

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

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

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

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

偽代碼