《图算法二.ppt》由会员分享，可在线阅读，更多相关《图算法二.ppt（23页珍藏版）》请在三一办公上搜索。
1、图算法（二）,最小生成树minimum spanning tree,最小生成树定义,问题背景：图模型中的边与边权重（开销，代价）关联的各种应用 航空领域:边-航线,权重-距离,价格或时间 电路:边-电线,权重-长度,开销或时间 工作规划:边-任务,权重-执行任务的时间开销,最小生成树定义,求开销最小值问题包含两类算法:(1)查找将所有点连接在一起的最低开销路径.最小生成树 多用于无向图(2)查找两个已知点之间的最低开销路经.最短路径 多用于有向图,最小生成树定义,生成树如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。图的生成树不惟一。最小生
2、成树 生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST,最小生成树,假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,取图中任意一个顶点 v（一般取第一个点）作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v
3、之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。,普里姆算法的基本思想:,例如:,a,e,d,c,b,g,f,14,8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,1）图采用邻接矩阵存储。2）第一个点为树根。2）找到目前情况下能连上的权值最小的边的另一端点，加入之，重复n-1次。,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下
4、所添加的顶点应满足下列条件:,设置一个辅助数组closedge，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,int clomaxv;,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,19 m m 14 m 1819 5 7 12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m 2718 m m m 16 27,1）顶点1作为树的根，初始化clo数组 cloi=map1i;2）从clo非0值中找最小值min以及对应的顶点k
5、;/cloi=0表示在树里或者与树无连接边3）mincost+=m;clok=0;4）通过顶点k，更新clo数组 if(cloimapki)cloi=mapki;5）重复2,3,4 n-1次。,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔算法的基本思想：,a,e,d,c,b,g,f,14,8,5,3,16,21,例如:,7,12,18,19,算法描述:,构造非连通图
6、 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第 i 条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v);且 k+;,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(nloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,问题描述 北极的某区域共有n座村庄(1 n 500)，每座村庄的坐标用一对整数(x,y)表示，其中 0 x,y 10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同
7、。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有k台（0 k 100）卫星设备，计算出应该如何分配这k台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每两座村庄之间都可以直接或间接地通讯。,例1：北极通讯网络,例如，对于下面三座村庄：,例1：北极通讯网络,例1：北极通讯网络,如果没有任何卫星设备或只有1台卫星设备（k=0或k=1），则满足条件的最小的d=20，因为A和B，B和C可以用无线电直接通
8、讯；而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：北极通讯网络,The End,
