最小生成树

来自计算思维百科
跳转至: 导航搜索

贪心策略也指导着实际工程建设,如铺设管道、光缆、建设公路等。假设要在n个城市之间铺设光缆,铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,问如何铺设,使得 n 个城市的任意两个之间都可以通信,且使铺设光缆的总费用最低。这一问题可用图论中的最小生成树求解,而求解最小生成树的两个算法都是贪心算法。

                      9.2.7.png


                                    图1 最小生成树

假设图1(a),图中顶点表示城市,边上权值表示两个城市之间铺设电缆的费用。

图的生成树含图中全部n个顶点,但只有边集合的n-1条边,且不构成回路,即生成树中任何两个顶点之间有路径。一个图的生成树不是唯一的,如图1(a)中选择AB、BC、DA三条边构成生成树,选择AC、AB、DC边也构成生成树。在图的所有生成树中边上权值之和最小的生成树称为图的'最小生成树'(Minimum Spanning Tree)。

用贪心法求解最小生成树,其中一种贪心选择策略是:贪心选择权值最小的边,若与之前加入的边构成回路,则放弃;否则,加入最小生成树。图1(a)的最小生成树计算过程为:

  1. 贪心选择边AD;
  2. 贪心选择边DC,不构成回路;
  3. 贪心选择边AC,构成回路A->D->C->A,放弃;
  4. 贪心选择边DB,不构成回路,结束。

图1(a)的最小生成树如图1(b)所示。最小生成树也可用在网络路由中。