数据结构15-最小生成树.ppt

《数据结构15-最小生成树.ppt》由会员分享，可在线阅读，更多相关《数据结构15-最小生成树.ppt（26页珍藏版）》请在三一办公上搜索。

1、,图的最小生成树,对于一张图进行深度优先搜索或宽度优先搜索，可生成一棵深度优先搜索树或宽度优先搜索树。搜索的出发点不同，生成树的形态亦不同。在一张有权连通图中，各边权和为最小的一棵生成树即为最小生成树。,计算最小生成树的思维方向：为了保证边权总和最小，必须保证、添加(u,v)不能够形成回路、在保证的前提下添加权尽可能小的，这样的边称之为安全边有两种算法可计算图的最小生成树、Kruskal算法、Prim算法,、Kruskal算法,找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。初始时，森林由单个结点组成的n棵树。,Kruskal程序,Cons

2、t maxn=200;maxe=maxn*maxn;/*顶点数和边数的上限*/Type edgetype=Record/*边的类型*/x,y,c:longint;/*边权为c的边（x，y）*/end;Var e:Array 1.maxe of edgetype;/*边集，其中第i条边为(ei.x,ei.y)，该边的权为ei.c*/n,m,ans:longint;/*顶点数为n，边数为m*/f:Array 1.maxn of longint;/*并查集。其中fi为顶点i所在并查集的代表顶点，即子树根*/,通过函数top(i)计算顶点i所在子树的根,func top(i:longint):long

3、int;/*计算和返回顶点i所在并查集的代表顶点*/if ifi Then fitop(fi);/*若i非所在并查集的代表顶点，则沿fi递归*/topfi;/*返回顶点i所在并查集的代表顶点*/;/*top*/,通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树,现有边权为c的边（i，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和v，则(i,j)加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。proc Union(i,j,c:longint);/*合并i和j所在集合*/Var x,y:longint;xtop(i);ytop(j);/*分别取出

4、顶点i和顶点j所在子树的根*/if xy Then inc(ans,c);fyx;/*若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并*/;/*Union*/,主算法,按照边权值（c域值）递增的顺序排序边集e；For i1 to n Do fii;/*建立由n棵树组成的森林，每棵树包含图的一个顶点*/ans0;/*最小生成树的权和初始化为0*/For i1 to m Do Union(ei.x,ei.y,ei.c);/*枚举每条边，将两个端点分属两棵树的边加入最小生成树*/Writeln(ans);显然,Kruskal算法的效率取决于边数m,因此适用与稀疏图。,、Prim算法

5、,集合A中的边总是只形成单棵树，每次添加到树中的边都是使树的权尽可能小的边。,设 di顶点i与生成树相连的最短边长；bai顶点i在生成树的标志；wi,j（i,j）的边长。若图中不存在边（i,j），则wi,j=min所有未在生成树的顶点的最小距离值,fillchar(ba，sizeof(ba)，0)；/*所有顶点未在生成树*/for i2 to n do di；/*所有顶点的距离值初始化*/d10；ans0；/*顶点1的距离值和生成树的权和初始化*/for i1 to n do/*依次范围每个顶点*/minmaxint；/*在所有未在生成树、且距离值最小（min）的顶点k*/for j1 to

6、n do if not bajand(djmin)then kj；mindj；/*then*/if min=maxint then ans-1；break；/*若这样的顶点不存在，则无解退出*/ansans+min；baktrue；/*最小距离值min计入生成树的权和,顶点k进入生成树*/for j1 to n do/*调整与k相连的各顶点的距离值*/minwk，j；if mindj then djmin；/*for*/；/*for*/writeln(ans：0：3)；/*输出最小生成树的权和*/,两种算法的比较,共同点：贪心，选择边权最小的安全边不同点：Kruskal算法在森林中的两 棵树之

7、间 添安全边；Prim算法在单棵树上添安全边。Kruskal算法的效率取决于边数m，因此适用于稀疏图；Prim算法的效率取决于顶点数n，因此适用于稠密图,计算最大边权最小的生成树,给出一个有边权的图，要求其中的一棵生成树，使得这棵生成树的最大边权最小。,图的最小生成树满足这个性质,反证法：反设图中存在一棵生成树T，T中的最大边权小于最小生成树Tmin的最大边权。令e是Tmin的最大边。e将Tmin分成两个连通分块X和Y。由于Tmin是最小生成树，那么图中连接X和Y的任意边e,其边权都大于等于e的边权结论1。而T是图的一棵生成树，那么T中的最大边e连接X和Y，按照假设,e的边权小于e的边权。这与

8、结论1矛盾，因此最小生成树最大边权最小的结论是成立的。因此只要用Prim或Kruscarl算法求出图的最小生成树即可。,北极通讯网络,北极的某区域共有n座村庄(1n500)，每座村庄的坐标用一对整数(x，y)表示，其中 0 x，y10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座

9、村庄无论相距多远都可以直接通讯。现在有k台（0k100）卫星设备，请你编一个程序，计算出应如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每两座村庄之间都可直接或间接地通讯。请输出最小d值,K=2B和C，min(d)=d(A,B)=10。,数据限制：n500，k100。,逆向思维,村庄设为顶点，所有可以互相通讯的村庄连边，边长为村庄间的距离，构造一个图。图中卫星设备的台数k就是图的连通支的个数，每个连通支内顶点间的边长不大于d。,已知k，求d，比较困难。已知d，求k，相对简单！,逆向思维,找到一个最小的d，使得连通支的个数小于等于卫星设备的数目k。,引理,如果去掉所有长度大

10、于d的边后，最小生成树被分成k个连通支，那么图也被分成k个连通支。,证明提示：反证法构造回路,证明,用反证法。假设原图被分割成k(kk)个连通支，显然kk。根据鸽巢原理,在某一连通支TK中，最小生成树被分成了至少两部分，不妨设其为T1，T2。因为T1和T2同属于一个连通支TK，所以一定存在xT1，yT2，w(x，y)d。又因为在整个最小生成树中，所以x到y的路径中一定存在一条权值大于d的边(u，v)（否则x和y就不会分属于T1和T2了），w(x，y)dw(u，v)，所以把(x，y)加入，把(u，v)去掉，将得到一棵总权值比最小生成树还小的生成树。这显然是不可能的。所以，原命题成立。（证毕）,可

11、行性。如果d等于第k长边的长度，将去掉前k-1长的边，最小生成树将被分成k个连通支。由引理，原图也将被分成k个连通支，满足连通支个数小于等于k的要求。最优性。如果d小于第k长边的长度，至少会去掉前k长的边，最小生成树至少被分成k+1个连通支，原图也至少被分成k+1个连通支，不满足要求。,构造:计算最小生成树的第k长边,动态生成最小生成树,在一个初始化为空的无向图中，不断加入新边。如果当前图连通，就求出当前图最小生成树的总权值；否则，输出-1。输入输出情况：第1行输入顶点数n和加入的边数k；以下为2*k行，其中第2*i行输入x y c,表示加入的第i条边连接顶点x和y，权值为c；第2*i+1行输

12、出回答：最小生成树的总权值（如果当前图连通），或者-1（如果当前图不连通）,两种解法,解法1:每加入一条边，重新计算最小生成树；解法2:在最小生成树中加边的基础上，求新的最小生成树。显然，解法2的时间效率明显优于解法1。由于生成树是具有n个点n-1条边的连通图，如果加入一条新边的话，势必会形成一个环。将环上任一条边删去（可以是新加进去的边），则会恢复生成树的结构。显然，为了保证是最小生成树，每次删除的边必须是环上的最长边。,初始化,const maxn=800;/*顶点数的上限*/var pnt:array1.maxnof integer;/*顶点i的父顶点为pnti*/e,c:array1.

13、maxn,0.maxn of integer;/*边表e，其中顶点i相连的边数为ei,0，第j条边的另一端点为ei,j，c为相邻矩阵*/n,k,sum,t:integer;/*顶点数为n新添边数为k，生成树的总权值为sum，边数为t*/xi,yi,max:integer;/*当前路径的最大边权为max,对应边为(xi,yi)*/ok:boolean;/*成功标志*/proc Init;/*输入信息*/var i:integer;readln(n,k);/*输入顶点数和加入的边数*/fillchar(e,sizeof(e),0);sum0;t0;/*边表、生成树的总权值和边数初始化*/for i

14、1 to n do pntii;/*n个顶点组成n棵树*/;/*Init*/,func find(x:integer):integer;/*返回x所在子树的根*/if xpntx then pntxfind(pntx);findpntx;/*find*/proc Ins(x,y,z:integer);/*将权为z的边(x,y)插入树中*/cx,yz;cy,xz;/*相邻矩阵增加边(x,y)*/inc(ex,0);ex,ex,0y;inc(ey,0);ey,ey,0 x;/*(x,y)进入边表*/;/*Ins*/proc Del(x,y:integer);/*将边(x,y)从树中删除*/var

15、i,j:integer;for i1 to ex,0 do/*在x相连的边中搜索(x,y)*/if ex,i=y/*y右方的同层顶点顺序左移,并退出循环,*/then for ji to ex,0-1 do ex,jex,j+1;break;/*then*/dec(ex,0);/*x的度数减1*/for i1 to ey,0 do/*在y相连的边中搜索(y,x)*/if ey,i=x/*x右方的同层顶点顺序左移,并退出循环*/then for ji to ey,0-1 do ey,jey,j+1;break;/*then*/dec(ey,0);/*y的度数-1*/;/*Del*/,proc c

16、heck(x,fa,y,dx,dy,d:integer);/*搜索x至y的路径上权值最大的边（fa为x的前驱顶点，目前路径的最大边权为d，对应边为（dx,dy）*/var i:integer;if x=y/*若搜索完x至y的路径,则返回成功标志、最大边权及其对应边*/then oktrue;xidx;yidy;maxd;exit/*then*/;for i1 to ex,0 do/*搜索x的每一个后趋顶点*/if ex,ifa then if cx,ex,id/*分情形递归*/then check(ex,i,x,y,x,ex,i,cx,ex,i)else check(ex,i,x,y,dx,d

17、y,d);if ok then exit;/*若成功找到最大边权，则退出*/;/*check*/,proc Make;/*插入k条边，计算和输出最小生成树*/var x,y,z，i,j,l:integer;for i1 to k do/*依次插入每条边*/readln(x,y,z);/*插入权为z的第i条边(x,y)*/if find(x)find(y)/*若x和y分属不同的子树,则插入边(x,y)*/then Ins(x,y,z);pntpntxpnty;/*x所在的子树并入y所在的子树*/inc(t);sumsum+z;/*累计边数与权值和*/else okfalse;check(x,-1,y,0,0,0);/*若x和y连通,则计算x至y间路径的最大边权max和对应的边(xi,yi)if maxz/*若最大边权大于z，则删除(xi,yi),加入新边(x,y)*/then Del(xi,yi);sumsum-cxi,yi;Ins(x,y,z);sumsum+z;/*then*/;/*else*/if t=n-1/*若图连通,则输出最小生成树的总权值，否则输出-1*/then writeln(sum)else writeln(-1);/*for*/;/*Make*/Init;/*输入信息*/Make;/*插入k条边，计算和输出最小生成树*/./*main*/,