生成树

图论中,无向图 G生成树英语:)是具有 G 的全部顶点,但边数最少的连通子图。[1]

格子图的生成树(图中的蓝色粗线)

表示顶点表示,若图 ,有,那么的生成树。

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

最小生成树

带权图的生成树中,总权重最小的称为最小生成树

求取最小生成树的算法:

  • 克鲁斯克尔算法 - 一种贪心算法,复杂度是
  • 普林姆算法 - 另一种贪心算法,用二叉堆优化时复杂度是 。当边数远远大于点数,可近似认为是
  1. . 第三版. : 362. ISBN 978-7-111-40701-0.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.