图的生成树基本概念

Published on 2016 - 06 - 20

树与森林

树(Tree):如果一个无向连通图中不存在回路,则这种图称为树,因此树是一种特殊的图。

例如,图1(a)所示的无向连通图存在回路,所以它不是一棵树。但可以从中去掉构成回路的边,如在图1(b)中去掉了边(1,4)和(6,7),这样图中就不存在回路了,因此该图就是一棵树。当然,去掉边(3,4)和(5,6)也可以构造一棵树。

为什么不存在回路的连通图被称为树呢?因为可以把这种图改画成一棵倒立的树。在图1(c)和1(d)中,分别将图1(b)改画成根为顶点4的树和根为顶点5的树。

森林

森林(Forest):如果一个无向图中包含了几棵树,那么该无向图可以称为森林。很明显森林是非连通图。例如,图2所示为一个包含3棵树的森林。

生成树及最小生成树

生成树

生成树(Spanning Tree):无向连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树。生成树是连通图的极小连通子图。这里所谓极小是指:若在树中任意增加一条边,则将出现一个回路;若去掉一条边,将会使之变成非连通图。

按照生成树的定义,包含n个顶点的连通图,其生成树有n个顶点、n-1条边。

根据图的遍历的知识可知,用不同的遍历方法遍历图,可以得到不同的生成树;从不同的顶点出发遍历图,也能得到不同的生成树。所以有时需要根据应用的需求选择合适的边构造一个生成树。

最小生成树

对于一个带权的无向连通图(即无向网)来说,如何找出一棵生成树,使得各边上的权值总和达到最小,这是一个有着实际意义的问题。例如,在n个城市之间建立通信网络,至少要架设n-1条线路,这时自然会考虑:如何选择这n-1条线路,使得总造价最少?

在每两个城市之间都可以架设一条通信线路,并要花费一定的代价。若用图的顶点表示n个城市,用边表示两个城市之间架设的通信线路,用边上的权值表示架设该线路的造价,就可以建立一个通信网络。对于这样一个有n个顶点的网络,可以有不同的生成树,每棵生成树都可以构成通信网络。现在希望能根据各边上的权值,选择一棵总造价最小的生成树,这就是最小生成树的问题。

最小生成树(Minimum Spanning Tree,MST)或者称为最小代价生成树 Minimum-cost Spannirng Tree:对无向连通图的生成树,各边的权值总和称为生成树的权,权最小的生成树称为最小生成树。

构造最小生成树的准则有3条。

  1. 必须只使用该网络中的边来构造最小生成树。
  2. 必须使用且仅使用n-1条边来连接网络中的n个顶点。
  3. 不能使用产生回路的边。

构造最小生成树的算法主要有:克鲁斯卡尔(Kruskal)算法、Boruvka算法和普里姆(Prim)算法,它们都得遵守以上准则。它们都采用了一种逐步求解的策略。

如果一个连通无向网为G(V,E),顶点集合V中有n个顶点。最初先构造一个包括全部n个顶点和0条边的森林Forest={T0,T1,…,Tn-1},以后每一步向Forest中加入一条边,它应当是一端在Forest中的某一棵树Ti上,而另一端不在Ti上的所有边中具有最小权值的边。由于边的加入,使Forest中的某两棵树合并为一棵。经过n-1步,最终得到一棵有n-1条边的、各边权值总和达到最小的生成树。

参考文档