生成树

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

以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) 。