對于一個帶權（假設每條邊上的權均為大于零的實數）連通無向圖 G 中的不同生成樹，其每棵樹的所有邊上的權值之和也可能不同；圖的所有生成樹中具有邊上的權值之和最小的樹稱為圖的最小生成樹（Minimal Spanning Tree）。

按照生成樹的定義，$n$ 個頂點的連通圖的生成樹有 $n$ 個頂點、$(n?1)$ 條邊。因此，構造最小生成樹的準則有以下 3 條：

1. 必須只使用該圖中的邊來構造最小生成樹；
2. 必須使用且僅使用 $(n?1)$ 條邊來連接圖中的 $n$ 個頂點；
3. 不能使用產生回路的邊。

構造最小生成樹有多種算法，其中多數算法利用了最小生成樹的下列一種簡稱為 MST 的性質：假設 $N=(V,E)$ 是一個連通網（帶權連通圖），$U$ 是頂點集 $V$ 的一個非空子集。若 $(u,v)$ 是一條具有最小權值（代價）的邊，其中 $ u\in U,~v\in V-U$ ，則必存在一棵包含邊 $(u,v)$ 的最小生成樹。

這個結論的證明，此處從略，可以參考《數據結構》（嚴蔚敏，人民郵電出版社）。

求圖的最小生成樹有很多實際應用，例如城市之間的交通工程造價最優問題就是一個最小生成樹問題。求圖的最小生成樹有兩個算法著名的算法：普里姆算法和克魯斯卡爾算法。

普里姆算法

普里姆算法的構造過程

普里姆（Prim）算法是一種構造最小生成樹的算法。

假設 $G=(V,E)$ 是一個具有 $n$ 個頂點的帶權連通圖，$T=(U,TE)$ 是 $G$ 的最小生成樹，其中 $U$ 是 $T$ 的頂點集，$TE$ 是 $T$ 的邊集，則由 $G$ 構造從起始點 $v$ 出發的最小生成樹 $T$ 的步驟如下:

1. 初始化 U = { v } U=\{v\} U={v} ，以 $v$ 到其他頂點的所有邊為候選邊。
2. 重復以下步驟 $(n?1)$ 次，使得其他 $(n?1)$ 個頂點被加入到 $U$ 中。
   • 從候選邊中挑選權值最小的邊加入 $TE$ ，設該邊在 $V?U$ 中的頂點是 $k$ ，將 $k$ 加入 $U$ 中；
   • 考査當前 $V?U$ 中的所有頂點 $j$ ，修改候選邊，若 $(k,i)$ 的權值小于原來和頂點 $j$ 關聯的候選邊，則用$(k,i)$ 取代后者作為候選邊。

例如，對于圖 8.4.7 所示帶權連通圖，假設起始點為頂點 0，采用普里姆算法構造最小生成樹。

圖 8.4.7 帶權連通圖

1. 最小生成樹 $T$ 包含所有頂點。
2. U = { 0 } , V ? U = { 1 , 2 , 3 , 4 , 5 , 6 } U=\{0\},~V-U=\{1,2,3,4,5,6\} U={0},?V?U={1,2,3,4,5,6} ，在這兩個頂點集之間選擇第 1 條最小邊 $(0,5)$ 添加到 $TE$ 中，即 $TE=\{(0,5)\}$。
3. U = { 0 , 5 } , V ? U = { 1 , 2 , 3 , 4 , 6 } U=\{0,5\},~V-U=\{1,2,3,4,6\} U={0,5},?V?U={1,2,3,4,6} ，在這兩個頂點集之間選擇第 2 條最小邊 $(5,4)$ 添加到 $TE$ 中，即 $TE=\{(0,5),(5,4)\}$。
4. U = { 0 , 5 , 4 } , V ? U = { 1 , 2 , 3 , 6 } U=\{0,5,4\},~V-U=\{1,2,3,6\} U={0,5,4},?V?U={1,2,3,6}? ，在這兩個頂點集之間選擇第 3 條最小邊 $(4,3)$? 添加到 $TE$? 中，即 $TE=\{(0,5),(5,4),(4,3)\}$?。
5. U = { 0 , 5 , 4 , 3 } , V ? U = { 1 , 2 , 6 } U=\{0,5,4,3\},~V-U=\{1,2,6\} U={0,5,4,3},?V?U={1,2,6}? ，在這兩個頂點集之間選擇第 4 條最小邊 $(3,2)$? 添加到 $TE$? 中，即 $TE=\{(0,5),(5,4),(4,3),(3,2)\}$?。
6. U = { 0 , 5 , 4 , 3 , 2 } , V ? U = { 1 , 6 } U=\{0,5,4,3,2\},~V-U=\{1,6\} U={0,5,4,3,2},?V?U={1,6}? ，在這兩個頂點集之間選擇第 5 條最小邊 $(2,1)$? 添加到 $TE$? 中，即 $TE=\{(0,5),(5,4),(4,3),(3,2),(2,1)\}$?。
7. U = { 0 , 5 , 4 , 3 , 2 , 1 } , V ? U = { 6 } U=\{0,5,4,3,2,1\},~V-U=\{6\} U={0,5,4,3,2,1},?V?U={6} ，在這兩個頂點集之間選擇第 6 條最小邊 $(1,6)$ 添加到 $TE$ 中，即 $TE=\{(0,5),(5,4),(4,3),(3,2),(2,1),(1,6)\}$，即得到了最小生成樹，如圖 8.4.8 所示。

圖 8.4.8 由普里姆算法得到的最小生成樹

如果每次選擇最小邊時，存在多條同樣權值的邊可選，則任選其一即可。

克魯斯卡爾算法

克魯斯卡爾（Kruskal）算法是一種按權值的遞增次序選擇合適的邊來構造最小生成樹的方法。

克魯斯卡爾算法的構造過程

假設 $G=(V,E)$ 是一個具有 $n$ 個頂點的帶權連通無向圖，$T=(U,TE)$ 是 $G$ 的最小生成樹，則構造最小生成樹的步驟如下：

1. 置 $U$ 的初值為 $V$ （即包含有 $G$ 中的全部頂點），$TE$ 的初值為空集（即圖 $T$ 中的每一個頂點都構成一個分量）。
2. 將圖 $G$ 中的邊按權值從小到大的順序依次選取，若選取的邊未使生成樹 $T$ 形成回路，則加入 $TE$ ，否則舍棄，直到 $TE$ 中包含 $(n?1)$ 條邊為止。

以圖 8.4.7 所示的帶權連通圖為例，采用克魯斯卡爾算法構造最小生成樹，其過程如下：

1. 將所有邊按權值遞增排序：(0,5), (2,3), (1,6), (1,2), (3,6), (3,4), (4,6), (4,5), (0,1) 。

2. 最小生成樹 $T$ 包含所有頂點。

3. 選最小的邊 (0,5) 加入到 $T$ 中，此時不會出現回路。

4. 選第 2 小的邊 (2,3) 加入到 $T$ 中，此時不出現回路。

5. 選第 3 小的邊 (1,6) 加入到 $T$ 中，此時不出現回路。

6. 選第 4 小的邊 (1,2) 加入到 $T$? 中，此時不出現回路。

7. 選第 5 小的邊 (3,6) 加入到 $T$ 中，此時出現回路，故舍棄它。選第 6 小的邊 (3,4) 加入到 $T$ 中，此時不出現回路。

8. 選第 7 小的邊 (4,6) 加入到 $T$ 中，此時出現回路，故舍棄它。選第 8 小的邊 (4,5) 加入到 $T$? 中，此時不出現回路。

   至此在 $T$ 中已經有 6 條邊（$n=7$），產生了最小生成樹，如圖 8.4.9 所示。

   

   圖 8.4.9 由克魯斯卡爾算法得到的最小生成樹

將這里用克魯斯卡爾算法所得到的最小生成樹，與上一節中用普里姆算法得到的最小生成樹對比，可以發現，二者結果相同。這在本例中是一個巧合。