最小生成树

图算法（二）最小生成树minimumspanningtree最小生成树定义●问题背景：图模型中的边与边权重（开销，代价）关联的各种应用航空领域:边-航线,权重-距离,价格或时间电路:边-电线,权重-长度,开销或时间工作规划:边-任务,权重-执行任务的时间开销最小生成树定义●求开销最小值问题包含两类算法:(1)查找将所有点连接在一起的最低开销路径.最小生成树多用于无向图(2)查找两个已知点之间的最低开销路经.最短路径多用于有向图最小生成树定义生成树如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。图的生成树不惟一。最小生成树生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(MinimumSpannirngTree)。最小生成树可简记为MST最小生成树假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？问题：构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。算法二：（克鲁斯卡尔算法）该问题等价于：算法一：（普里姆算法）取图中任意一个顶点v（一般取第一个点）作为生成树的根，之后往生成树上添加新的顶点w。在添加的顶点w和已经在生成树上的顶点v之间必定存在一条边，并且该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。普里姆算法的基本思想:abcdegf195141827168213127例如:aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=671）图采用邻接矩阵存储。2）第一个点为树根。2）找到目前情况下能连上的权值最小的边的另一端点，加入之，重复n-1次。在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足下列条件:UV-U设置一个辅助数组closedge，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：intclo[maxv];abcdegf1951418271682131270123456clovcloaedcbaaa19141814例如:e12ee8168d3dd7213c5519mm14m18195712mmm53mmmm73821m1412m8m16mmm21m2718mmm16271）顶点1作为树的根，初始化clo数组clo[i]=map[1][i];2）从clo非0值中找最小值min以及对应的顶点k;//clo[i]==0表示在树里或者与树无连接边3）mincost+=m;clo[k]=0;4）通过顶点k，更新clo数组if(clo[i]map[k][i])clo[i]=map[k][i];5）重复2,3,4n-1次。如何输出具体边的信息？具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：abcdegf195141827168213127aedcbgf148531621例如:7121819算法描述:构造非连通图ST=(V,{});k=i=0;//k计选中的边数while(kn-1){++i;检查边集E中第i条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且k++;}普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法[问题描述]北极的某区域共有n座村庄(1n500)，每座村庄的坐标用一对整数(x,y)表示，其中0x,y10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有k台（0k100）卫星设备，计算出应该如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每两座村庄之间都可以直接或间接地通讯。例1：北极通讯网络例如，对于下面三座村庄：例1：北极通讯网络ABCA(10,10)B(10,0)C(30,0)||10||20||105ABBCAC例1：北极通讯网络如果没有任何卫星设备或只有1台卫星设备（k=0或k=1），则满足条件的最小的d=20，因为A和B，B和C可以用无线电直接通讯；而A和C可以用B中转实现间接通讯（即消息从A传到B，再从B传到C）；如果有2台卫星设备（k=2），则可以把这两台设备分别分配给B和C，这样最小的d可取10，因为A和B之间可以用无线电直接通讯；B和C之间可以用卫星直接通讯；A和C可以用B中转实现间接通讯。如果有3台卫星设备，则A,B,C两两之间都可以直接用卫星通讯，最小的d可取0。知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。把所有可以互相通讯的村庄连接起来，构成一个图。卫星设备的台数就是图的连通支的个数。问题转化为：找到一个最小的d，使得把所有权值大于d的边去掉之后，连通支的个数小于等于k。例1：北极通讯网络定理2：如果去掉所有权值大于d的边后，最小生成树被分割成为k个连通分支，图也被分割成为k个连通分支。得到构造算法：最小生成树的第k长边就是问题的解。例1：北极通讯网络TheEnd