生成树此条目需要补充更多来源。 (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.
