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


IOI2004 国家集训队论文 吴景岳 第 1 页 共 29 页 最小生成树算法及其应用 江苏省常州高级中学 吴景岳 【摘要】 最小生成树是图论中的经典问题,也是一个重要部分,一般书上 往往只介绍求最小生成树的算法,而忽略了更精彩的算法应用部分。 本文将对最小生成树算法及其应用作全面的分析说明,使大家对此有 更加深刻的认识。本文分三部分:一、基础篇,主要介绍基础概念、 求最小生成树的一般算法和常用算法。二、应用篇,具体问题具体分 析,侧重于思考和证明的过程。三、总结。 【关键字】 最小生成树 【目录】 一、 基础篇 1.定义 2.求最小生成树的一般算法 3.常用算法 a) Kruskal 算法 b) Prim 算法 4.Maintain——IOI2003 二、 应用篇 1.概述 2.例题 a) Robot——BOI2002 b) 北极通讯网络——Waterloo University 2002 三、 总结 IOI2004 国家集训队论文 吴景岳 第 2 页 共 29 页 【正文】 1.基础篇 1.1 定义 在电路设计中,常常需要把一些电子元件的插脚用电线连接起来。如果每根 电线连接两个插脚,把所有 n 个插脚连接起来,只要用 n-1 根电线就可以了。在 所有的连接方案中,我们通常对电线总长度最小的连接方案感兴趣。 把问题转化为图论模型就是:一个无向连通图 G=(V,E),V 是插脚的集合, E 是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值 w(u,v),表示 连接它们所需的电线长度。我们的目标就是找到一个无环的边集 T,连接其中所 有的点且使总权值最小。 总权值 å Î = Tvu vuwTw ),( ),()( 既然 T 是连接所有点的无环边集,它一定是一棵树。因为这棵树是从图 G 中生成出来的,我们把它叫做生成树。如果一棵生成树在所有生成树中总权值最 小,我们就把它称作最小生成树。 1.2 求最小生成树的一般算法 解决最小生成树问题有没有一般的方法呢?下面我们就介绍一种贪心算法。 该算法设置了集合 A,该集合一直是某最小生成树的子集。算法执行的每一步, 都要决策是否把边(u,v)添加到集合 A 中,能够添加的条件是保证 A∪{(u,v)}仍然 是最小生成树的子集。我们称像(u,v)这样的边为 A 的安全边,或称这样的边对 集合 A 是安全的。 求最小生成树的一般算法流程如下: GENERIC-MST(G,w) 1. A←Ф 2. while A 没有形成一棵生成树 3. do 找出 A 的一条安全边(u,v) 4. A←A∪{(u,v)} 5. return A 一开始 A 为Ф,显然满足最小生成树子集的条件。之后,每一次循环都把 一条 A 的安全边加入 A 中,A 依然是最小生成树。 本节的余下部分将提出一条确认安全边的规则(定理 1),下一节将具体讨 论运用这一规则寻找安全边的两个有效的算法。 IOI2004 国家集训队论文 吴景岳 第 3 页 共 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)}。 下一步我们证明 T’是一棵最小生成树。因为(u,v)是通过割(S,V-S)的一条轻 边,且边(x,y)也通过割,所以有 w(u,v)≤w(x,y),因此 w(T’)=w(T)-w(x,y)+w(u,v) IOI2004 国家集训队论文 吴景岳 第 4 页 共 29 页 ≤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. do MAKE-SET(v) IOI2004 国家集训队论文 吴景岳 第 5 页 共 29 页 4. 根据权 w 的非递减顺序对 E 的边进行排序 5. for 每条边(u,v)∈E,按权的非递减次序 6. do if FIND-SET(u)≠FIND-SET(v) 7. then A←A∪{(u,v)} 8. UNION(u,v) 9. return A Kruskal 算法的工作流程如图 3 所示。阴影覆盖的边属于正在生成的森林 A。 算法按权的大小顺序考察各边。箭头指向算法每一步所考察到的边。第 1-3 行初 始化集合 A 为空集并建立|V|棵树,每棵树包含图的一个结点。在第 4 行中根据 其权值非递减次序对 E 的边进行排序。在第 5-8 行的 for 循环中首先检查对每条 边(u,v)其端点 u 和 v 是否属于同一棵树。如果是,则把(u,v)加入森林就会形成一 回路,所以这时放弃边(u,v);如果不是,则两结点分属不同的树,由第 7 行把边 加入集合 A 中,第 8 行对两颗树中的结点进行归并。 IOI2004 国家集训队论文 吴景岳 第 6 页 共 29 页 图 3 Kruskal 算法的执行流程 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}} IOI2004 国家集训队论文 吴景岳 第 7 页 共 29 页 图 4 Prim 算法的执行流程 MST-PRIM(G,w,r) 1. Q←V[G] 2. for 每个 u∈Q 3. do key[u]←∞ 4. key[r]←0 5. π[r]←NIL 6. while Q<>Ф 7. do u←EXTRACT-MIN(Q) {返回队列 Q 中最小的元素} 8. for 每个 v∈Adj[u] 9. do if v∈Q and w(u,v)k,所以 k’1 Do Begin i:=j div 2; If h[i].cost<=x.cost Then Break; h[j]:=h[i]; pos[h[j].point]:=j; j:=i; End; h[j]:=x; pos[x.point]:=j; End; Procedure Go_Down(i:longint);{堆中元素向下调整} Var x:rtype; j:longint; Begin x:=h[i]; While i+i<=htail Do Begin j:=i+i; If (jnil Do Begin j:=p^.data; If (pos[j]<>-1) and (p^.costf[i] Then f[i]:=top(f[i]); top:=f[i]; End; Procedure Union(i,j,c:longint);{合并 i 和 j 所在集合} Var x,y:longint; Begin x:=top(i); y:=top(j); If x<>y Then Begin Inc(ans,c); f[y]:=x; End; End; Procedure Main;{主过程} Var i:longint; Begin Qksort(1,m); For i:=1 to n Do f[i]:=i; ans:=0; For i:=1 to m Do Union(e[i].x,e[i].y,e[i].c); End; Procedure Answer;{输出} Begin Assign(output,outputfile); Rewrite(output); Writeln(ans); Close(output); End; IOI2004 国家集训队论文 吴景岳 第 20 页 共 29 页 Begin Init; Main; Answer; End. 附录三:Maintain 源程序 Program Maintenance; Const maxn=200; Type rtype=Record{Prim 算法中队列元素的类型} point,cost:longint; End; Var a:Array [1..maxn,1..maxn] of longint;{用邻接矩阵表示边集} dep,f:array [1..maxn] of longint;{每个点在最小生成树中的深度即父亲结点} edge,n,m,i,j,cost,k,max,mi,mj,ans:longint; Function Connected:boolean;{判断当前图是否连通} Var q:Array [1..maxn] of longint; visit:Array [1..maxn] of boolean; head,tail,i,j:longint; Begin Fillchar(visit,Sizeof(visit),0); head:=1; tail:=1; q[1]:=1; visit[1]:=true; While head<=tail Do Begin i:=q[head]; For j:=1 to n Do If not(visit[j]) and (a[i,j]>0) Then Begin visit[j]:=true; Inc(tail); q[tail]:=j; End; Inc(head); End; Connected:=(tail=n); End; IOI2004 国家集训队论文 吴景岳 第 21 页 共 29 页 Procedure MST;{用 Prim 算法求最小生成树} Var b:Array [1..maxn] of rtype; i,j,temp,tot:longint; tb:rtype; Begin Fillchar(f,Sizeof(f),0); For i:=1 to n Do Begin b[i].point:=i; If i=1 Then b[i].cost:=0 Else b[i].cost:=maxlongint; End; For i:=1 to n-1 Do Begin For j:=i+1 to n Do If b[j].cost0) and (tempdep[j] Do i:=f[i]; While dep[i]j Do Begin i:=f[i]; j:=f[j] End; k:=i;{k 是 I 和 j 的深度最大的共同祖先} i:=backupi; j:=backupj; While i<>k Do Begin If a[i,f[i]]>max Then Begin max:=a[i,f[i]]; mi:=f[i]; mj:=i; End; i:=f[i]; End; While j<>k Do Begin If a[j,f[j]]>max Then Begin max:=a[j,f[j]]; mi:=f[j]; mj:=j; End; j:=f[j]; End; End; Procedure DFS(i:longint);{用深度优先得到一棵搜索树,也即最小生成树} Var j:longint; Begin For j:=1 to n Do If (j<>f[i]) and (a[i,j]>0) Then Begin f[j]:=i; DFS(j); End; IOI2004 国家集训队论文 吴景岳 第 23 页 共 29 页 End; Begin Assign(input,'maintain.in'); Assign(output,'maintain.out'); Reset(input); Rewrite(output); Read(n,m); Fillchar(a,Sizeof(a),0); For edge:=1 to m Do{不断读入新边,直到连通为止} Begin Read(i,j,a[i,j]); a[j,i]:=a[i,j]; If Connected Then Begin MST; Break; End Else Writeln(-1); End; While edgecost Then{如果 I 到 j 路径上的最长边大于新边长度,立即更新} Begin a[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;{得到最小生成树的总权值} For k:=2 to n Do Inc(ans,a[k,f[k]]); Writeln(ans); End; Close(output); Close(input); End. IOI2004 国家集训队论文 吴景岳 第 24 页 共 29 页 附录四:Robot 源程序 program Robot; const maxm=30; maxn=100; type ptype=record{点的类型} x,y:longint; end; rtype=record{队列中元素的类型} point,cost:longint; end; var w1,w2:array [1..maxm+1] of ptype;{走廊的墙壁} p:array [1..maxn] of ptype;{障碍物} a:array [1..maxn+2,1..maxn+2] of longint;{用邻接矩阵存放所有的边} b:array [1..maxn+2] of rtype;{队列} f:array [1..maxn+2] of longint;{最小生成树中每个点的父亲结点} m,i,n,j,temp,k,ans:longint; tb:rtype; function min(a,b:longint):longint; begin if ab then max:=a else max:=b; end; begin assign(input,'robot.in');{文件读入} assign(output,'robot.out'); reset(input); read(m); for i:=1 to m+1 do read(w1[i].x,w1[i].y); for i:=1 to m+1 do read(w2[i].x,w2[i].y); read(n); for i:=1 to n do read(p[i].x,p[i].y); close(input); IOI2004 国家集训队论文 吴景岳 第 25 页 共 29 页 {建边的过程,程序中点 1~n 表示障碍物,n+1 和 n+2 表示走廊的墙壁} for i:=1 to n+2 do for j:=1 to n+2 do a[i,j]:=maxlongint; for j:=1 to n do for i:=1 to m do begin if w1[i].x=w1[i+1].x then if (p[j].y-w1[i].y)*(p[j].y-w1[i+1].y)<=0 then temp:=abs(w1[i].x-p[j].x) else temp:=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))) else if (p[j].x-w1[i].x)*(p[j].x-w1[i+1].x)<=0 then temp:=abs(w1[i].y-p[j].y) else temp:=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))); if tempn+1 do begin if a[i,f[i]]>ans then ans:=a[i,f[i]]; i:=f[i]; end; rewrite(output); writeln(ans); close(output); IOI2004 国家集训队论文 吴景岳 第 27 页 共 29 页 end. 附录五:“北极通讯网络”源程序 Program Network; Const inputfile='input.txt'; outputfile='output.txt'; maxn=500; maxnum=1e+20; Type ptype=Record{平面上点的类型} x,y:longint; End; rtype=Record{队列元素的类型} point:longint; cost:real; End; Var a:Array [1..maxn,1..maxn] of real;{两点间的距离} p:Array [1..maxn] of ptype;{平面上所有的点} f:Array [1..maxn] of longint;{最小生成树中每个点的父亲结点} b:Array [1..maxn] of rtype;{队列} e:Array [1..maxn] of real;{最小生成树中的所有边} n,k:longint; Function Dis(x1,y1,x2,y2:longint):real;{两点间的距离} Begin Dis:=Sqrt(Sqr(x1-x2)+Sqr(y1-y2)); End; Procedure Init;{初始化} Var i,j:longint; Begin Assign(input,inputfile); Reset(input); Read(n,k); If k<1 Then k:=1; If k>n Then k:=n; For i:=1 to n Do Read(p[i].x,p[i].y); Close(input); For i:=1 to n Do For j:=1 to n Do IOI2004 国家集训队论文 吴景岳 第 28 页 共 29 页 a[i,j]:=Dis(p[i].x,p[i].y,p[j].x,p[j].y); End; Procedure MST;{用 Prim 算法求最小生成树} Var i,j:longint; temp:real; tb:rtype; Begin Fillchar(f,Sizeof(f),0); For i:=1 to n Do Begin b[i].point:=i; If i=1 Then b[i].cost:=0 Else b[i].cost:=maxnum; End; For i:=1 to n-1 Do Begin For j:=i+1 to n Do If b[j].cost=e[j]) Do Dec(j); e[i]:=e[j]; While (i=k) Do Inc(i); e[j]:=e[i]; End; e[i]:=k; If i=pos Then Find:=k Else If i
还剩28页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

彼时离岸

贡献于2012-07-23

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!