最小生成樹：一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。
最小生成樹可以用kruskal（克魯斯卡爾）算法或PRim（普里姆）算法求出。
在一給定的無向圖G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊，而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集且為無循環圖，使得的 w(T) 最小，則此 T 為 G 的最小生成樹。最小生成樹其實是最小權重生成樹的簡稱。例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。
Prim算法簡述
1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；2).初始化：Vnew= {x}，其中x為集合V中的任一節點（起始點），Enew= {},為空；3).重復下列操作，直到Vnew= V：a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，并且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；b.將v加入集合Vnew中，將<u, v>邊加入集合Enew中；4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。圖例描述:
| 圖例 | 說明 | 不可選 | 可選 | 已選（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).新建圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).將原圖Graph中所有e個邊按權值從小到大排序
4).循環：從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節點都在同一個連通分量中
if （這條邊連接的兩個節點于圖Graphnew中不在同一個連通分量中）
添加這條邊到圖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。最后成功的圖就是右：
新聞熱點
疑難解答
