生成树此条目需要补充更多来源。 (2020年3月8日)请协助补充多方面可靠来源以改善这篇条目,无法查证的内容可能会因为异议提出而移除。致使用者:请搜索一下条目的标题(来源搜索:"生成树" — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。在图论中,无向图 G 的生成树(英语:Spanning Tree)是具有 G 的全部顶点,但边数最少的连通子图。[1] 格子图(英语:grid graph)的生成树(图中的蓝色粗线) 以 V {\displaystyle V} 表示顶点, E {\displaystyle E} 表示边,若图 G = ( V ( G ) , E ( G ) ) {\displaystyle G=(V(G),E(G))} 和树 T = ( V ( T ) , E ( T ) ) {\displaystyle T=(V(T),E(T))} ,有 E ( T ) ⊂ E ( G ) {\displaystyle E(T)\subset E(G)} 和 V ( G ) = V ( T ) {\displaystyle V(G)=V(T)} ,那么 T {\displaystyle T} 是 G {\displaystyle G} 的生成树。 一个图的生成树可能有多个。 最小生成树 带权图的生成树中,总权重最小的称为最小生成树。 求取最小生成树的算法: 克鲁斯克尔算法 - 一种贪心算法,复杂度是 O ( E log E ) {\displaystyle O(E\log {E})} 。 普林姆算法 - 另一种贪心算法,用二叉堆优化时复杂度是 O ( E + V log V ) {\displaystyle O(E+V\log {V})} 。当边数远远大于点数,可近似认为是 O ( E ) {\displaystyle O(E)} 。^ 第23章. 算法导论 第三版. : 362. ISBN 978-7-111-40701-0.