《图算法二备课讲稿》由会员分享，可在线阅读，更多相关《图算法二备课讲稿（23页珍藏版）》请在金锄头文库上搜索。
1、图算法（二）,最小生成树 minimum spanning tree,最小生成树定义,问题背景： 图模型中的边与边权重（开销，代价）关联的各种应用 航空领域: 边-航线, 权重-距离,价格或时间 电路: 边-电线, 权重-长度,开销或时间 工作规划: 边-任务, 权重-执行任务的时间开销,最小生成树定义,求开销最小值问题包含两类算法: (1) 查找将所有点连接在一起的最低开销路径. 最小生成树 多用于无向图 (2) 查找两个已知点之间的最低开销路经. 最短路径 多用于有向图,最小生成树定义,生成树如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree
2、)。 图的生成树不惟一。 最小生成树 生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST,构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。,算法二：（克鲁斯卡尔算法）,该问题等价于：,算法一：（普里姆算法）,取图中任意一个顶点 v（一般取第一个点） 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，
3、直至生成树上含有 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中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,设置一个辅助数组closedge，对当前VU集中的每个顶点，记录和顶
4、点集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 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14 12 m 8 m 16 m m m 21 m 27 18 m m m 16 27,1）顶点1作为树的根，初始化clo数组 cloi=map1i; 2）从clo非0值中找最小值min以及对应的顶点k; /cloi=0表示在树里或者与树无连接边 3）mincost+=m; clok=0;
5、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,算法描述:,构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数 wh
6、ile (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可以用无线电直接通讯；而A和C可以用B中转
8、实现间接通讯（即消息从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,
