算法合集之《最小生成树算法及其应用》

《算法合集之《最小生成树算法及其应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IOI2004国家集训队论文吴景岳最小生成树算法及其应用江苏省常州高级中学吴景岳【摘要】最小生成树是图论中的经典问题,也是一个重要部分，一般书上往往只介绍求最小生成树的算法，而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明，使大家对此有更加深刻的认识。本文分三部分：一、基础篇，主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇，具体问题具体分析，侧重于思考和证明的过程。三、总结。【关键字】最小生成树【目录】一、基础篇1．定义2．求最小生成树的一般算法3．常用算法a)Kruskal算法b)Prim算法4．Maint

2、ain——IOI2003二、应用篇1．概述2．例题a)Robot——BOI2002b)北极通讯网络——WaterlooUniversity2002三、总结第1页共29页IOI2004国家集训队论文吴景岳【正文】1．基础篇1．1定义在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只要用n-1根电线就可以了。在所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。把问题转化为图论模型就是：一个无向连通图G=(V,E)，V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边(u,v)一

3、个权值w(u,v)，表示连接它们所需的电线长度。我们的目标就是找到一个无环的边集T，连接其中所有的点且使总权值最小。总权值w(T)=åw(u,v)(u,v)ÎT既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图G中生成出来的，我们把它叫做生成树。如果一棵生成树在所有生成树中总权值最小，我们就把它称作最小生成树。1．2求最小生成树的一般算法解决最小生成树问题有没有一般的方法呢？下面我们就介绍一种贪心算法。该算法设置了集合A，该集合一直是某最小生成树的子集。算法执行的每一步，都要决策是否把边(u,v)添加到集合A中，能够添加的条件是保证A∪{(

4、u,v)}仍然是最小生成树的子集。我们称像(u,v)这样的边为A的安全边，或称这样的边对集合A是安全的。求最小生成树的一般算法流程如下：GENERIC-MST(G,w)1.A←Ф2.whileA没有形成一棵生成树3.do找出A的一条安全边(u,v)4.A←A∪{(u,v)}5.returnA一开始A为Ф，显然满足最小生成树子集的条件。之后，每一次循环都把一条A的安全边加入A中，A依然是最小生成树。本节的余下部分将提出一条确认安全边的规则（定理1），下一节将具体讨论运用这一规则寻找安全边的两个有效的算法。第2页共29页IOI2004国家集训队论文吴景岳图

5、1一个图的割(S,V-S)首先定义几个概念。有向图G=(V,E)的割(S,V-S)是V的一个分划。当一条边(u,v)∈E的一个端点属于S而另一端点属于V-S，我们说边(u,v)通过割(S,V-S)。若集合A中没有边通过割，就说割不妨碍集合A。如果某边是通过割的具有最小权值的边，则称该边为通过割的一条轻边。如图1，集合S中的结点为黑色结点，集合V-S中的结点为白色结点。连接白色和黑色结点的那些边为通过该割的边。从边上所标的权值看，边(d,c)为通过该割的唯一一条轻边。子集A包含阴影覆盖的那些边，注意，由于A中没有边通过割，所以割(S,V-S)不妨碍A。确

6、认安全边的规则由下列定理给出。定理1设图G(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的一个子集且包含于G的某个最小生成树中，割(S,V-S)是G的不妨碍A的任意割且边(u,v)是穿过割(S,V-S)的一条轻边，则边(u,v)对集合A是安全的。证明：设T是包含A的一最小生成树。如果T包含轻边（u,v），则T包含A∪{(u,v)}，证明就完成了。否则，可设法建立另一棵包含A∪{(u,v)}的最小生成树T’，(u,v)对集合A仍然是安全的。图2最小生成树T’的建立图2示出了最小生成树T’的建立。S中的结点为黑色，V-S中的结点为

7、白色，边(u,v)与T中从u到v的通路P构成一回路。由于边(u,v)通过割(S,V-S)，因此在T中的通路P上至少存在一条边也通过这个割。设(x,y)为满足此条件的边。因为割不妨碍A，所以边(x,y)不属于A。又因为(x,y)处于T中从u到v的唯一通路上，所以去掉边(x,y)就会把T分成两个子图。这时加入边(u,v)以形成一新的生成树T’=(T-{(x,y)})∪{(u,v)}。下一步我们证明T’是一棵最小生成树。因为(u,v)是通过割(S,V-S)的一条轻边，且边(x,y)也通过割，所以有w(u,v)≤w(x,y)，因此w(T’)=w(T)-w(x,

8、y)+w(u,v)第3页共29页IOI2004国家集训队论文吴景岳≤w(T)。但T是最小生成树