生成树：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2024年7月21日 (日) 11:40的最新版本

在图论中，無向圖 G 的生成树（英語：Spanning Tree）是具有 G 的全部顶点，但边数最少的連通子圖。^[1]

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

这是一篇電腦科學小作品。您可以通过编辑或修订扩充其内容。

^ 第23章. 算法导论第三版. : 362. ISBN 978-7-111-40701-0.

[1] 第23章. 算法导论第三版. : 362. ISBN 978-7-111-40701-0.

[1]

@@ 第1行： / 第1行： @@
+{{Refimprove|time=2020-03-08T07:07:49+00:00}}
-V表示顶点，E表示边，若[[图]]G=(V(G),E(G))和[[树]]T=(V(T),E(T))，有E(T)⊂E(G)和V(G)=V(T)，那么T是G的生成树。
+[[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:图论]]