查看“︁生成树”︁的源代码

{{Refimprove|time=2020-03-08T07:07:49+00:00}}
[[File:4x4 grid spanning tree.svg|thumb|{{le|格子圖|grid graph}}的生成樹（圖中的藍色粗線）]]
[[File:Натурализация гамильтоновых циклов.jpg|thumb|8x8网格图上的三个例子]]
在[[图论]]中，[[图_(数学)|無向圖]] ''G'' 的'''生成树'''（{{lang-en|Spanning Tree}}）是具有 ''G'' 的全部[[顶点 (图论)|顶点]]，但边数最少的連通子圖。<ref>{{Cite book|title=算法导论|isbn=978-7-111-40701-0|pages=362|edition=第三版|chapter=第23章}}</ref>

以<math>V</math>表示[[顶点 (图论)|顶点]]，<math>E</math>表示[[邊 (圖論)|边]]，若图 <math>G=(V(G),E(G))</math>和[[树_(图论)|树]]<math>T=(V(T),E(T))</math>，有<math>E(T)\subset E(G)</math>和<math>V(G)=V(T)</math>，那么<math>T</math>是<math>G</math>的生成树。

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

== 最小生成树 ==
[[图论术语#带权图与网络|带权图]]的生成树中，总权重最小的称为'''[[最小生成树]]'''。

求取最小生成树的算法：

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

{{计算机科学小作品}}

[[Category:选择公理]]
[[Category:图论]]