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

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

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

Prim算法簡述

圖例描述:

圖例	說明	不可選	可選	已選（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被高亮表示。	C	B, 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

算法簡單描述

1).記Graph中有v個頂點，e個邊

2).新建圖Graph_new，Graph_new中擁有原圖中相同的e個頂點，但沒有邊

3).將原圖Graph中所有e個邊按權值從小到大排序

4).循環：從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節點都在同一個連通分量中

                if （這條邊連接的兩個節點于圖Graph_new中不在同一個連通分量中）

                添加這條邊到圖Graph_new中

圖例描述：

首先第一步，我們有一張圖Graph，有若干點和邊 

將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這里再次體現了貪心算法的思想。資源排序，對局部最優的資源進行選擇，排序完成后，我們率先選擇了邊AD。這樣我們的圖就變成了右圖

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

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

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

偽代碼