第七章 树算法.docx

第十三章 树算法§ 13 ．1 导 言树(tree)在图论中是相当重要的一类图，它非常类似于自然界中的树，图13. l(a)就 是一个树图的例子．树的性质非常好，应用相当广泛．例如，可用树图来形象地表示家族(见 图13. (b))、行政组织机构；可用材图来列举排列；用树来分析游戏中的策略；计算机用树 来描述运算顺序，用树来组织其拥有的资源以便于查找；在编译程序中，用树来表示源程序本章不讨论上述这些应用，主要讨论在设计具有某种最优性的网络方面起重要作用的最小生 成材及其算法.图论中的算法设计与分析是一个非常引人入胜的领域，是一个激发洞察力的 领域在这一章将会给出许多特色各异的算法，你将会看到Pim算法和Kruskal算法的历史; Pim 算法和 Kruskal 算法的各种不同应用；穷举法、贪婪法、试探法以及这些算法设计基本 方法的灵活应用；如何修改算法以适应于改变了的问题.§ 13 .2、引例：计算机网络的线路设计城市电信局有许多业务，如收费、营业、 112、 114 等，希望在全市范围实现计算机联 网服务，共享各种资源，比如，数据库资源.一个主要关心的问题是：用数据通讯线把一组 站点联结起来，而不允许通讯线在非站点处连接，如何连接可使通讯线的花费最少？任意两 个站点可经过若干中介站点取得联系.为简便起见，以一个小型的问题为例.假设各站点间可以铺设通讯线路进行连接的情况如图13.2所示，顶点为站点，边为连接两站点之间的通讯线，边的权为其费用.c • /Ti■ 13.2我们的目的是要找到图13. 2的一个连接所有顶点的具有最小总权数的连通子图.先介 绍几个术语.连通图(connected graph):任意两点之间都有路径的图.如图13. 2就是一个连通图.圈(cycle)当一条路径的起点和终点是同一顶点时，称这条路径为圈.如图13. 2中的 路线1 - 2 - 5 - 4 - 1就是一个圈.事实上，在最经济的网络中，不应该有任何圈.否则，去掉圈上的一条边，这圈上任意 两个顶点仍能取得联系，正如在橡筋圈上剪一刀后，仍然是一个整段.树(tree):没有圈的连通图称为树.如图13. 1中的两个图都是树.*1* *1* *1* *1* *1* *1* *1**1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*^1* *1* *1* *1* *1* *1* *1* *1*rT* rT* rT* rlS rT» rTw提示: 1)树具有许多非常好的性质，这些性质包括A) 树中任意两点间有唯一路径B) 树的边数恰好等于顶点数减1.C) 在树中任意去掉一条边，将会不连通.D) 树中任意两个不相邻顶点间添一边后，就恰好含一个圈.2) 要将n个点连接起来至少需要n-1条边。

1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* ^1* *1* *1* *1* *1* *1* *1* *1*rT* rT* rT* rlS rT» rTw图G的子图(subgraph):由G的一些边和一些顶点组成，它是G的一个部分图，且必须满足：当一条边在子图时，这条边的两个端点也要在子图中．生成树或支樟树(spanning tree)： G是树的子图，其顶点集等于G的顶点集.如图13. 3中的两个图均是图13. 2的生成树.显然，每个生成树对应的线路费用都低于原图对应的线路费用，且生成树中没有多余边， 随意去掉其中的一条边都会破坏其连通性.因此，确定应在哪些站点之间铺设通讯线路，就可看作是在相应的加权图中构造最小费 用的生成树的问题.一般地，定义生成树的权为其上所有边权之和.最小生成树(minimum-weight spanning tree)：在一个加权连通图G中，权最小的那棵 生成树称为 G 的最小生成树.最大生成树(maximum-weight spanning tree):在一个加权连通图G中，权最大的那棵 生成树称为 G 的最大生成树.*1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* ^1* *1* *1* *1* *1* *1* *1* *1*rT* rT* rT* rlS rT» rTw注意一个简单连通图只要不是树，其生成树就不唯一，甚至非常多.如 10 个顶点的 完全图，其不同的生成树就有一亿棵.一般地，n个顶点的完全图，其不同的生成树个数为 n n 2*1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* ^1* *1* *1* *1* *1* *1* *1* *1*rT* rT* rT* rlS rT» rTw要求出最小生成树，一般不能用穷举法. 30个顶点的完全图就有3028 个生成树， 3028有 42 位，即使应用最现代的计算机，在我们有生之年也是无法穷举的，穷举法是无效算法， 坏算法.必须寻求其他的有效算法，这将在下一节介绍.如果允许通讯线可以在规定的站点以外的其他地方连接，得到的问题为Steiner树问题， 它比最小生成树问题更复杂，这将在后面介绍.与计算机网络设计相类似的问题还有许多，如 有线电视网、电线网、石油传输管网以 及其他的管道网，铁路、公路的建设等等.§ 13 .3 最小生成树算法在这一节，我们将介绍求最小生成树的两个算法：Prim算法和Kruskal算法，它们都蕴 涵了贪婪法的思想.*1* *1* *1* *1* *1* *1* *1* *1*、!*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *X* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*、1*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1***T» rT» rT* rT* rT* rTx提示贪婪法是一种可被用于各种各样问题的处理，它把解看成是由若干个部件构成， 每一步求出解的一个部分，但这不是从整体或长远的角度去考虑的，只是局部或当前的最好 选择.求出的一个个部件组合而作为最终的解.注意： 贪婪法只是一种试探法，计算上方便、有效，可提供正确解的一个近似。

但一 般情况下，不能保证输出的解是正确的，其正确性需要证明，这往往比较困难.*1* *1* *1* *1* *1* *1* *1* *1* vt*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *X* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* vt*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1***T» rT» rT* rT* rT* rTx13.3.1 Kruskal 算法假设给定了一个加权连通图G, G的边集合为E,顶点个数为nKruskal于1956年证 明了，按下述贪婪法总可得到G的一棵最小生成树T.Kruskal 算法的粗略描述为直观，假设T中的边和顶点均涂成红色，其余边为白色.一开始G中的边均为白色.1) 将所有顶点涂成红色；2) 在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；3) 重复2)直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合.*1* *1* *1* *1* *1* *1* *1* *1*、!*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *X* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*、1*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t*、t* *1* *1* *1* *1* *1* **T» rT» rT* rT* rT* rTx：加用上述方法在图上手工操作，求出图 13.2 的最小生成树。

^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx ^Tx手工操作时，第 2 步中，判断是否形成圈一眼就可看出，但计算机实现就不是那么直接． 注意到在算法执行过程中，红色顶点和红色边会形成一个或者一个以上的连通分支，它 们都是 G 的子树．一条边与红色边形成因当且仅当这条边的两个端点属于同一个子树．因 此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树．上述判断可这样实现：给每个子树一个不同的编号，对每一个顶点引入一个标记t,表 示这个顶点所在的子树编号．当加人一条红色边，就会使该边两端点所在的两个子树连接起 来，成为一个子树，从而两个子树中的顶点标记要改变成一样.综上，可将Kruskal算法细 化使其更容易计算机实现．变量说明：c :生成树的费用；T：生成树的边集合；j：迭代次数；k：记录已经被选人生成树的边数.Kruskal 算法：输入加权连通图G的边权矩阵[b(i, j)]，顶点数n.m x 31) 整理边权矩阵将[b(i, j)] 按第三行由小到。