生成树

在图论中，无向图 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)$ 。