![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/4x4_grid_spanning_tree.svg/langzh-640px-4x4_grid_spanning_tree.svg.png&w=640&q=50)
生成树
維基百科,自由的 encyclopedia
在图论中,無向圖 G 的生成树(英語:Spanning Tree)是具有 G 的全部顶点,但边数最少的連通子圖。[1]
此條目需要补充更多来源。 (2020年3月8日) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/4x4_grid_spanning_tree.svg/220px-4x4_grid_spanning_tree.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/93/%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg/640px-%D0%9D%D0%B0%D1%82%D1%83%D1%80%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2%D1%8B%D1%85_%D1%86%D0%B8%D0%BA%D0%BB%D0%BE%D0%B2.jpg)
一个图的生成树可能有多个。
最小生成树
求取最小生成树的算法:
![]() | 这是一篇電腦科學小作品。您可以通过编辑或修订扩充其内容。 |
- 第23章. 算法导论 第三版. : 362. ISBN 978-7-111-40701-0.
在图论中,無向圖 G 的生成树(英語:Spanning Tree)是具有 G 的全部顶点,但边数最少的連通子圖。[1]
此條目需要补充更多来源。 (2020年3月8日) |
一个图的生成树可能有多个。
求取最小生成树的算法:
![]() | 这是一篇電腦科學小作品。您可以通过编辑或修订扩充其内容。 |