生成樹

在圖論中，無向圖 G 的生成樹（英語：Spanning Tree）是具有 G 的全部頂點，但邊數最少的連通子圖。

格子圖的生成樹（圖中的藍色粗線）

8x8網格圖上的三個例子

以$V$表示頂點，$E$表示邊，若圖 $G=(V(G),E(G))$和樹$T=(V(T),E(T))$，有$E(T)\subset E(G)$和$V(G)=V(T)$，那麼$T$是$G$的生成樹。

一個圖的生成樹可能有多個。

最小生成樹

帶權圖的生成樹中，總權重最小的稱為最小生成樹。

求取最小生成樹的算法：

• 克魯斯克爾演算法 - 一種貪心算法，複雜度是 $O(E\log {E})$。
• 普林姆算法 - 另一種貪心算法，用二叉堆優化時複雜度是 $O(E+V\log {V})$。當邊數遠遠大於點數，可近似認為是 $O(E)$ 。