生成树

在图论中，無向圖 G 的生成树（英語：Spanning Tree）是具有 G 的全部顶点，但边数最少的連通子圖。

以${\displaystyle V}$表示顶点，${\displaystyle E}$表示边，若图 ${\displaystyle G=(V(G),E(G))}$和树${\displaystyle T=(V(T),E(T))}$，有${\displaystyle E(T)\subset E(G)}$和${\displaystyle V(G)=V(T)}$，那么${\displaystyle T}$是${\displaystyle G}$的生成树。

一个图的生成树可能有多个。

最小生成树

带权图的生成树中，总权重最小的称为最小生成树。

求取最小生成树的算法：

• 克鲁斯克尔演算法 - 一种贪心算法，复杂度是 ${\displaystyle O(E\log {E})}$。
• 普林姆算法 - 另一种贪心算法，用二叉堆优化时复杂度是 ${\displaystyle O(E+V\log {V})}$。当边数远远大于点数，可近似认为是 ${\displaystyle O(E)}$ 。

1. 第23章. 算法导论 第三版. : 362. ISBN 978-7-111-40701-0.