数据结构15-最小生成树

,图的最小生成树,对于一张图进行深度优先搜索或宽度优先搜索，可生成一棵深度优先搜索树或宽度优先搜索树。搜索的出发点不同，生成树的形态亦不同。在一张有权连通图中，各边权和为最小的一棵生成树即为最小生成树。,计算最小生成树的思维方向：为了保证边权总和最小，必须保证、添加(u,v)不能够形成回路、在保证的前提下添加权尽可能小的，这样的边称之为安全边有两种算法可计算图的最小生成树、Kruskal算法、Prim算法,、Kruskal算法,找出森林中连结任意两棵树的所有边中具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。初始时，森林由单个结点组成的n棵树。,Kruskal程序,Constmaxn=200;maxe=maxn*maxn;/*顶点数和边数的上限*/Typeedgetype=Record/*边的类型*/x,y,c:longint;/*边权为c的边（x，y）*/end;Vare:Array1.maxeofedgetype;/*边集，其中第i条边为(ei.x,ei.y)，该边的权为ei.c*/n,m,ans:longint;/*顶点数为n，边数为m*/f:Array1.maxnoflongint;/*并查集。其中fi为顶点i所在并查集的代表顶点，即子树根*/,通过函数top(i)计算顶点i所在子树的根,functop(i:longint):longint;/*计算和返回顶点i所在并查集的代表顶点*/ififiThenfitop(fi);/*若i非所在并查集的代表顶点，则沿fi递归*/topfi;/*返回顶点i所在并查集的代表顶点*/;/*top*/,通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树,现有边权为c的边（i，j）。若该边的两个端点分属于两棵树，顶点i和顶点j所在子树的根分别为x和v，则(i,j)加入最小生成树，合并两棵树（即顶点i和顶点j所在的并查集）。procUnion(i,j,c:longint);/*合并i和j所在集合*/Varx,y:longint;xtop(i);ytop(j);/*分别取出顶点i和顶点j所在子树的根*/ifxyTheninc(ans,c);fyx;/*若i和j分属于两棵子树，则该边权计入最小生成树的权和，两棵子树合并*/;/*Union*/,主算法,按照边权值（c域值）递增的顺序排序边集e；Fori1tonDofii;/*建立由n棵树组成的森林，每棵树包含图的一个顶点*/ans0;/*最小生成树的权和初始化为0*/Fori1tomDoUnion(ei.x,ei.y,ei.c);/*枚举每条边，将两个端点分属两棵树的边加入最小生成树*/Writeln(ans);显然,Kruskal算法的效率取决于边数m,因此适用与稀疏图。,、Prim算法,集合A中的边总是只形成单棵树，每次添加到树中的边都是使树的权尽可能小的边。,设di顶点i与生成树相连的最短边长；bai顶点i在生成树的标志；wi,j（i,j）的边长。若图中不存在边（i,j），则wi,j=min所有未在生成树的顶点的最小距离值,fillchar(ba，sizeof(ba)，0)；/*所有顶点未在生成树*/fori2tondodi；/*所有顶点的距离值初始化*/d10；ans0；/*顶点1的距离值和生成树的权和初始化*/fori1tondo/*依次范围每个顶点*/minmaxint；/*在所有未在生成树、且距离值最小（min）的顶点k*/forj1tondoifnotbajand(djmin)thenkj；mindj；/*then*/ifmin=maxintthenans-1；break；/*若这样的顶点不存在，则无解退出*/ansans+min；baktrue；/*最小距离值min计入生成树的权和,顶点k进入生成树*/forj1tondo/*调整与k相连的各顶点的距离值*/minwk，j；ifmindjthendjmin；/*for*/；/*for*/writeln(ans：0：3)；/*输出最小生成树的权和*/,两种算法的比较,共同点：贪心，选择边权最小的安全边不同点：Kruskal算法在森林中的两棵树之间添安全边；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的边权。这与结论1矛盾，因此最小生成树最大边权最小的结论是成立的。因此只要用Prim或Kruscarl算法求出图的最小生成树即可。,北极通讯网络,北极的某区域共有n座村庄(1n500)，每座村庄的坐标用一对整数(x，y)表示，其中0x，y10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有k台（0k100）卫星设备，请你编一个程序，计算出应如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每两座村庄之间都可直接或间接地通讯。请输出最小d值,K=2B和C，min(d)=d(A,B)=10。,数据限制：n500，k100。,逆向思维,村庄设为顶点，所有可以互相通讯的村庄连边，边长为村庄间的距离，构造一个图。图中卫星设备的台数k就是图的连通支的个数，每个连通支内顶点间的边长不大于d。,已知k，求d，比较困难。已知d，求k，相对简单！,逆向思维,找到一个最小的d，使得连通支的个数小于等于卫星设备的数目k。,引理,如果去掉所有长度大于d的边后，最小生成树被分成k个连通支，那么图也被分成k个连通支。,证明提示：反证法构造回路,证明,用反证法。假设原图被分割成k(kk)个连通支，显然kz/*若最大边权大于z，则删除(xi,yi),加入新边(x,y)*/thenDel(xi,yi);sumsum-cxi,yi;Ins(x,y,z);sumsum+z;/