论文--最小生成树算法及其应用.doc

最小生成树算法及其应用【摘要】最小生成树是图论中的经典问题,也是一个重要部分,一般书上往往只介绍求最小生成树的算法,而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明,使大家对此有更加深刻的认识。本文分三部分:一、基础篇,主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇,具体问题具体分析,侧重于思考和证明的过程。三、总结。【关键字】最小生成树【目录】基础篇定义求最小生成树的一般算法常用算法Kruskal算法Prim算法Maintain——IOI2003应用篇概述例题Robot——BOI2002北极通讯网络——WaterlooUniversity2002总结【正文】,常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚,把所有n个插脚连接起来,只要用n-1根电线就可以了。在所有的连接方案中,我们通常对电线总长度最小的连接方案感兴趣。把问题转化为图论模型就是:一个无向连通图G=(V,E),V是插脚的集合,E是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值w(u,v),表示连接它们所需的电线长度。我们的目标就是找到一个无环的边集T,连接其中所有的点且使总权值最小。总权值既然T是连接所有点的无环边集,它一定是一棵树。因为这棵树是从图G中生成出来的,我们把它叫做生成树。如果一棵生成树在所有生成树中总权值最小,我们就把它称作最小生成树。?下面我们就介绍一种贪心算法。该算法设置了集合A,该集合一直是某最小生成树的子集。算法执行的每一步,都要决策是否把边(u,v)添加到集合A中,能够添加的条件是保证A∪{(u,v)}仍然是最小生成树的子集。我们称像(u,v)这样的边为A的安全边,或称这样的边对集合A是安全的。求最小生成树的一般算法流程如下:GENERIC-MST(G,w)A←ФwhileA没有形成一棵生成树do找出A的一条安全边(u,v)A←A∪{(u,v)}returnA一开始A为Ф,显然满足最小生成树子集的条件。之后,每一次循环都把一条A的安全边加入A中,A依然是最小生成树。本节的余下部分将提出一条确认安全边的规则(定理1),下一节将具体讨论运用这一规则寻找安全边的两个有效的算法。图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。确认安全边的规则由下列定理给出。定理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中的结点为白色,边(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,y)+w(u,v)≤w(T)。但T是最小生成树,因此T’必定也是最小生成树。又因为T’包含A∪{(u,v)},所以(u,v)对A是安全的。(证毕)通过定理1可以更好地了解算法GENERIC-MST在连通图G=(V,E)上的执行流程。在算法执行过程中,集合A始终是无回路的,否则包含A的最小生成树就会出现一个环,这是不可能的。在算法执行中的任何一时刻,图GA=