生成树

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

以表示顶点，表示边，若图 和树，有和，那么是的生成树。

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

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

求取最小生成树的算法：

 克鲁斯克尔演算法 - 一种贪心算法，复杂度是 。
 普林姆算法 - 另一种贪心算法，用二叉堆优化时复杂度是 。当边数远远大于点数，可近似认为是  。

Category:选择公理
Category:图论