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

《论文--最小生成树算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

最小生成树算法及其应用最小生成树算法及其应用【摘要】最小生成树是图论中的经典问题,也是一个重要部分，一般书上往往只介绍求最小生成树的算法，而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明，使大家对此有更加深刻的认识。本文分三部分：一、基础篇，主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇，具体问题具体分析，侧重于思考和证明的过程。三、总结。【关键字】最小生成树【目录】一、基础篇1．定义2．求最小生成树的一般算法3．常用算法a)Kruskal算法b)Prim算法4．Maintain——IOI2003二、应用篇1．概述2．例题a)Robot——BOI2002b)北极通讯网络——WaterlooUniversity2002三、总结第29页共29页 最小生成树算法及其应用【正文】1．基础篇1．1定义在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只要用n-1根电线就可以了。在所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。把问题转化为图论模型就是：一个无向连通图G=(V,E)，V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值w(u,v)，表示连接它们所需的电线长度。我们的目标就是找到一个无环的边集T，连接其中所有的点且使总权值最小。总权值既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图G中生成出来的，我们把它叫做生成树。如果一棵生成树在所有生成树中总权值最小，我们就把它称作最小生成树。1．2求最小生成树的一般算法解决最小生成树问题有没有一般的方法呢？下面我们就介绍一种贪心算法。该算法设置了集合A，该集合一直是某最小生成树的子集。算法执行的每一步，都要决策是否把边(u,v)添加到集合A中，能够添加的条件是保证A∪{(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），下一节将具体讨论运用这一规则寻找安全边的两个有效的算法。第29页共29页 最小生成树算法及其应用图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)}。第29页共29页 最小生成树算法及其应用下一步我们证明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=(V,A)是一森林且GA的每一连通支均为树。此外，对A安全的任何边(u,v)都连接GA中不同的连通支，这是由于A∪{(u,v)}必定不包含回路。随着最小生成树的|V|-1条边相继被确定，GENERIC-MST中第2-4行的循环也随之要执行|V|-1次。初始状态下，A=Ф，GA中有|V|棵树，每个迭代过程均将减少一棵树，当森林中只包含一棵树时，算法执行终止。下面再来看一个由定理1得出的推论，下一节中论述的两种算法均使用了这个推论。推论1设G=(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的子集且包含于G的某个生成树中，C为森林GA=(V,A)中的连通支。若边(u,v)是连接C和GA中其它某连通支的一轻边，则边(u,v)对集合A是安全的。证明：因为割(C,V-C)不妨碍A，因此(u,v)是该割的一条轻边。由定理1，边(u,v)对集合A是安全的。（证毕）1．3常用算法GENERIC-MST是形成最小生成树的一般算法，不过我们需要的是更加具体的算法。这一节具体讨论两种常用的算法：Kruskal算法和Prim算法。它们虽然都遵循所谓的“一般”算法，但在实现上有着各自的特点。Kruskal算法：Kruskal算法是直接建立在上一节中给出的一般最小生成树算法的基础之上的。该算法找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。设C1和C2表示边(u,v)连结的两棵树。因为(u,v)必是连结C1和其它某棵树的一条轻边，所以由推论1可知(u,v)对C1是安全边。Kruskal算法是一种贪心算法，因为算法每一步添加到森林中的边的权值都尽可能小。Kruskal算法的实现可以使用并查集。每一集合包含当前森林中某个树的结点，操作FIND-SET(u)返回包含u的集合中的一个代表元素，因此我们可以通过测试FIND-SET(u)是否等同于FIND-SET(v)来确定两结点u和v是否属于同一棵树，通过过程UNION来完成树与树的连结。MST-KRUSKAL(G,w)1.A←Ф2.for每个结点v∈V[G]3.doMAKE-SET(v)第29页共29页 最小生成树算法及其应用1.根据权w的非递减顺序对E的边进行排序2.for每条边(u,v)∈E，按权的非递减次序3.doifFIND-SET(u)≠FIND-SET(v)4.thenA←A∪{(u,v)}5.UNION(u,v)6.returnAKruskal算法的工作流程如图3所示。阴影覆盖的边属于正在生成的森林A。算法按权的大小顺序考察各边。箭头指向算法每一步所考察到的边。第1-3行初始化集合A为空集并建立|V|棵树，每棵树包含图的一个结点。在第4行中根据其权值非递减次序对E的边进行排序。在第5-8行的for循环中首先检查对每条边(u,v)其端点u和v是否属于同一棵树。如果是，则把(u,v)加入森林就会形成一回路，所以这时放弃边(u,v)；如果不是，则两结点分属不同的树，由第7行把边加入集合A中，第8行对两颗树中的结点进行归并。第29页共29页 最小生成树算法及其应用图3Kruskal算法的执行流程Kruskal算法在图G=(V,E)上的运行时间取决于如何实现集合的合并。我们可以采用路径压缩的优化方法，这是目前所知的最有效的。初始化需占用时间O(V)，第4行中对边进行排序需要的运行时间为O(ElgE)；对分离集的森林要进行O(E)次操作，总共需要时间为O(Eα(E,V))，其中α函数为Ackermann函数的反函数。因为α(E,V)=O(lgE)。所以Kruskal算法的全部运行时间为O(ElgE)。Prim算法：正如Kruskal算法一样。Prim算法也是最小生成树一般算法的特例。它的执行非常类似于寻找图的最短通路的Dijkstra算法。Prim算法的特点是集合A中的边总是只形成单棵树。如图4所示，阴影覆盖的边属于正在生成的树，树中的结点为黑色。在算法的每一步，树中与树外的结点确定了图的一个割，并且通过该割的轻边被加进树中。树从任意根结点r开始形成并逐渐生长直至该树跨越了V中的所有结点。在每一步，连接A中某结点到V-A中某结点的轻边被加入到树中。由推论1，该规则总是加入对A安全的边，因此当算法终止时，A中的边就成为一棵最小生成树。因为每次添加到树中的边都是使树的权尽可能小的边，因此上述策略是“贪心”的。有效实现Prim算法的关键是设法较容易地选择一条新的边添加到由A的边所形成的树中，在下面的伪代码中，算法的输入是连通图G和将生成的最小生成树的根r。在算法执行过程中，不在树中的所有结点都驻留于优先级基于key域的队列Q中，对每个结点v，key[v]是连结v到树中结点的边所具有的最小权值；按常规，若不存在这样的边则key[v]=∞。域π[v]表示点v的“父亲结点”。在算法执行中，GENERIC-MST的集合A隐含地满足：A={(v,π[v]):v∈V-{r}-Q}当算法终止时，优先队列Q为空，因此G的最小生成树A满足：A={(v,π[v]):v∈V-{r}}第29页共29页 最小生成树算法及其应用图4Prim算法的执行流程MST-PRIM(G,w,r)1.Q←V[G]2.for每个u∈Q3.dokey[u]←∞4.key[r]←05.π[r]←NIL6.whileQ<>Ф7.dou←EXTRACT-MIN(Q){返回队列Q中最小的元素}8.for每个v∈Adj[u]9.doifv∈Qandw(u,v)k，所以k’1DoBegini:=jdiv2;Ifh[i].cost<=x.costThenBreak;h[j]:=h[i];pos[h[j].point]:=j;j:=i;End;h[j]:=x;pos[x.point]:=j;End;ProcedureGo_Down(i:longint);{堆中元素向下调整}Varx:rtype;j:longint;Beginx:=h[i];Whilei+i<=htailDoBeginj:=i+i;If(jnilDoBeginj:=p^.data;If(pos[j]<>-1)and(p^.costf[i]Thenf[i]:=top(f[i]);top:=f[i];End;ProcedureUnion(i,j,c:longint);{合并i和j所在集合}Varx,y:longint;Beginx:=top(i);y:=top(j);Ifx<>yThenBeginInc(ans,c);f[y]:=x;End;End;ProcedureMain;{主过程}Vari:longint;BeginQksort(1,m);Fori:=1tonDof[i]:=i;ans:=0;Fori:=1tomDoUnion(e[i].x,e[i].y,e[i].c);End;ProcedureAnswer;{输出}BeginAssign(output,outputfile);Rewrite(output);Writeln(ans);Close(output);End;第29页共29页 最小生成树算法及其应用BeginInit;Main;Answer;End.附录三：Maintain源程序ProgramMaintenance;Constmaxn=200;Typertype=Record{Prim算法中队列元素的类型}point,cost:longint;End;Vara:Array[1..maxn,1..maxn]oflongint;{用邻接矩阵表示边集}dep,f:array[1..maxn]oflongint;{每个点在最小生成树中的深度即父亲结点}edge,n,m,i,j,cost,k,max,mi,mj,ans:longint;FunctionConnected:boolean;{判断当前图是否连通}Varq:Array[1..maxn]oflongint;visit:Array[1..maxn]ofboolean;head,tail,i,j:longint;BeginFillchar(visit,Sizeof(visit),0);head:=1;tail:=1;q[1]:=1;visit[1]:=true;Whilehead<=tailDoBegini:=q[head];Forj:=1tonDoIfnot(visit[j])and(a[i,j]>0)ThenBeginvisit[j]:=true;Inc(tail);q[tail]:=j;End;Inc(head);End;Connected:=(tail=n);End;第29页共29页 最小生成树算法及其应用ProcedureMST;{用Prim算法求最小生成树}Varb:Array[1..maxn]ofrtype;i,j,temp,tot:longint;tb:rtype;BeginFillchar(f,Sizeof(f),0);Fori:=1tonDoBeginb[i].point:=i;Ifi=1Thenb[i].cost:=0Elseb[i].cost:=maxlongint;End;Fori:=1ton-1DoBeginForj:=i+1tonDoIfb[j].cost0)and(tempdep[j]Doi:=f[i];Whiledep[i]jDoBegini:=f[i];j:=f[j]End;k:=i;{k是I和j的深度最大的共同祖先}i:=backupi;j:=backupj;Whilei<>kDoBeginIfa[i,f[i]]>maxThenBeginmax:=a[i,f[i]];mi:=f[i];mj:=i;End;i:=f[i];End;Whilej<>kDoBeginIfa[j,f[j]]>maxThenBeginmax:=a[j,f[j]];mi:=f[j];mj:=j;End;j:=f[j];End;End;ProcedureDFS(i:longint);{用深度优先得到一棵搜索树，也即最小生成树}Varj:longint;BeginForj:=1tonDoIf(j<>f[i])and(a[i,j]>0)ThenBeginf[j]:=i;DFS(j);End;第29页共29页 最小生成树算法及其应用End;BeginAssign(input,'maintain.in');Assign(output,'maintain.out');Reset(input);Rewrite(output);Read(n,m);Fillchar(a,Sizeof(a),0);Foredge:=1tomDo{不断读入新边，直到连通为止}BeginRead(i,j,a[i,j]);a[j,i]:=a[i,j];IfConnectedThenBeginMST;Break;EndElseWriteln(-1);End;WhileedgecostThen{如果I到j路径上的最长边大于新边长度，立即更新}Begina[mi,mj]:=0;a[mj,mi]:=0;a[i,j]:=cost;a[j,i]:=cost;Fillchar(f,Sizeof(f),0);DFS(1);End;ans:=0;{得到最小生成树的总权值}Fork:=2tonDoInc(ans,a[k,f[k]]);Writeln(ans);End;Close(output);Close(input);End.第29页共29页 最小生成树算法及其应用附录四：Robot源程序programRobot;constmaxm=30;maxn=100;typeptype=record{点的类型}x,y:longint;end;rtype=record{队列中元素的类型}point,cost:longint;end;varw1,w2:array[1..maxm+1]ofptype;{走廊的墙壁}p:array[1..maxn]ofptype;{障碍物}a:array[1..maxn+2,1..maxn+2]oflongint;{用邻接矩阵存放所有的边}b:array[1..maxn+2]ofrtype;{队列}f:array[1..maxn+2]oflongint;{最小生成树中每个点的父亲结点}m,i,n,j,temp,k,ans:longint;tb:rtype;functionmin(a,b:longint):longint;beginifabthenmax:=aelsemax:=b;end;beginassign(input,'robot.in');{文件读入}assign(output,'robot.out');reset(input);read(m);fori:=1tom+1doread(w1[i].x,w1[i].y);fori:=1tom+1doread(w2[i].x,w2[i].y);read(n);fori:=1tondoread(p[i].x,p[i].y);close(input);第29页共29页 最小生成树算法及其应用{建边的过程，程序中点1~n表示障碍物，n+1和n+2表示走廊的墙壁}fori:=1ton+2doforj:=1ton+2doa[i,j]:=maxlongint;forj:=1tondofori:=1tomdobeginifw1[i].x=w1[i+1].xthenif(p[j].y-w1[i].y)*(p[j].y-w1[i+1].y)<=0thentemp:=abs(w1[i].x-p[j].x)elsetemp:=min(max(abs(p[j].x-w1[i].x),abs(p[j].y-w1[i].y)),max(abs(p[j].x-w1[i+1].x),abs(p[j].y-w1[i+1].y)))elseif(p[j].x-w1[i].x)*(p[j].x-w1[i+1].x)<=0thentemp:=abs(w1[i].y-p[j].y)elsetemp:=min(max(abs(p[j].x-w1[i].x),abs(p[j].y-w1[i].y)),max(abs(p[j].x-w1[i+1].x),abs(p[j].y-w1[i+1].y)));iftempn+1dobeginifa[i,f[i]]>ansthenans:=a[i,f[i]];i:=f[i];end;rewrite(output);writeln(ans);close(output);第29页共29页 最小生成树算法及其应用end.附录五：“北极通讯网络”源程序ProgramNetwork;Constinputfile='input.txt';outputfile='output.txt';maxn=500;maxnum=1e+20;Typeptype=Record{平面上点的类型}x,y:longint;End;rtype=Record{队列元素的类型}point:longint;cost:real;End;Vara:Array[1..maxn,1..maxn]ofreal;{两点间的距离}p:Array[1..maxn]ofptype;{平面上所有的点}f:Array[1..maxn]oflongint;{最小生成树中每个点的父亲结点}b:Array[1..maxn]ofrtype;{队列}e:Array[1..maxn]ofreal;{最小生成树中的所有边}n,k:longint;FunctionDis(x1,y1,x2,y2:longint):real;{两点间的距离}BeginDis:=Sqrt(Sqr(x1-x2)+Sqr(y1-y2));End;ProcedureInit;{初始化}Vari,j:longint;BeginAssign(input,inputfile);Reset(input);Read(n,k);Ifk<1Thenk:=1;Ifk>nThenk:=n;Fori:=1tonDoRead(p[i].x,p[i].y);Close(input);Fori:=1tonDoForj:=1tonDo第29页共29页 最小生成树算法及其应用a[i,j]:=Dis(p[i].x,p[i].y,p[j].x,p[j].y);End;ProcedureMST;{用Prim算法求最小生成树}Vari,j:longint;temp:real;tb:rtype;BeginFillchar(f,Sizeof(f),0);Fori:=1tonDoBeginb[i].point:=i;Ifi=1Thenb[i].cost:=0Elseb[i].cost:=maxnum;End;Fori:=1ton-1DoBeginForj:=i+1tonDoIfb[j].cost=e[j])DoDec(j);e[i]:=e[j];While(i=k)DoInc(i);e[j]:=e[i];End;e[i]:=k;Ifi=posThenFind:=kElseIfi