最小生成树学习.pptx

《最小生成树学习.pptx》由会员分享，可在线阅读，更多相关《最小生成树学习.pptx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树定义最小生成树定义问题背景：问题背景：图模型中的边与边权重（开销，代价）关联的各种应图模型中的边与边权重（开销，代价）关联的各种应用用 航空领域航空领域:边边-航线航线,权重权重-距离距离,价格或时间价格或时间 电路电路:边边-电线电线,权重权重-长度长度,开销或时间开销或时间 工作规划工作规划:边边-任务任务,权重权重-执行任务的时间开销执行任务的时间开销第1页/共24页最小生成树定义最小生成树定义求开销最小值问题包含两类算法求开销最小值问题包含两类算法:(1)(1)查找将所有点连接在一起的最低开销路径查找将所有点连接在一起的最低开销路径.最小生成树最小生成树 多用于多用于无向图无

2、向图 (2)(2)查找两个已知点之间的最低开销路经查找两个已知点之间的最低开销路经.最短路径最短路径 多用于多用于有向图有向图第2页/共24页最小生成树定义最小生成树定义生成树生成树如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。图的生成树不惟一。最小生成树最小生成树 生成树T各边的权值总和称为该树的权;权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST 第3页/共24页 最小生成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节

3、省经费的前提下如何在最节省经费的前提下建立建立这个通讯网通讯网？问题：问题：第4页/共24页 构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）第5页/共24页 取图中任意一个顶点取图中任意一个顶点 v（一般取第一个点）（一般取第一个点）作为生成树的根，之后往生成树上添加新的顶作为生成树的根，之后往生成树上添加新的顶点点 w。在添加的顶点在添加的顶点 w 和已经在生成树上的顶和已经在生成树上的顶点点v 之间必定

4、存在一条边，并且该边的权值在所之间必定存在一条边，并且该边的权值在所有连通顶点有连通顶点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后。之后继续往生成树上添加顶点，直至生成树上含有继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:第6页/共24页abcdegf195141827168213127例如例如:aedcbgf148531621所得生成树权值和=14+8+3+5+16+21=67第7页/共24页1）图采用邻接矩阵存储。2）第一个点为树根。2）找到目前情况下能连上的权值最小的边的另一端点，加入之，重复n-1次。

5、第8页/共24页 在生成树的构造过程中，图中在生成树的构造过程中，图中 n 个个顶点分属两个集合：顶点分属两个集合：已落在生成树上的已落在生成树上的顶点集顶点集 U 和尚未落在生成树上的顶点集和尚未落在生成树上的顶点集V-U，则应在所有连通，则应在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小的边。顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足下列一般情况下所添加的顶点应满足下列条件条件:UV-U第9页/共24页 设置一个辅助数组设置一个辅助数组closedge，对当前，对当前VU集中的每个顶点，记录和顶点集集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：中顶点

6、相连接的代价最小的边：int clomaxv;第10页/共24页abcdegf195141827168213127aedcbaaa19141814例如例如:e12ee8168d3dd7213c5 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第11页/共24页1）顶点1作为树的根，初始化clo数组 cloi=map1i;2）从clo非0值中找最小值min以及对应的顶点k;/cloi=0表示在树里或者与树无连接边3）mincost+=m;clok=0;

7、4）通过顶点k，更新clo数组 if(cloimapki)cloi=mapki;5）重复2,3,4 n-1次。第12页/共24页如何输出具体边的信息？第13页/共24页具体做法具体做法:先构造一个只含先构造一个只含 n 个顶点的子图个顶点的子图 SG，然后从权值最小的边开始，若它的添，然后从权值最小的边开始，若它的添加不使加不使SG 中产生回路，则在中产生回路，则在 SG 上加上这上加上这条边，如此重复，直至加上条边，如此重复，直至加上 n-1 条边为止。条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上为使生成树上边的权边的权值之和达到最小值之和达到最小，则应使生成树中每一条，则应使生

8、成树中每一条边的权值尽可能地小。边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：第14页/共24页abcdegf195141827168213127aedcbgf148531621例如例如:7121819第15页/共24页算法描述算法描述:构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn-1)+i;检查边集 E 中第第 i 条权值最小的边条权值最小的边(u,v);若若(u,v)加入加入ST后不使后不使ST中产生回路中产生回路，则则 输出边输出边(u,v);且且 k+;第16页/共24页普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂

9、度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法第17页/共24页问题描述问题描述北极的某区域共有北极的某区域共有n座村庄座村庄(1 n 500)，每座村庄的坐，每座村庄的坐标用一对整数标用一对整数(x,y)表示，其中表示，其中0 x,y 10000。为了加强联系，。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有且所有的无线电收发机型号相同。但卫

10、星设备数量有限，只能给一部分村庄的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。配备卫星设备。不同型号的无线电收发机有一个不同的参数不同型号的无线电收发机有一个不同的参数d，两座村庄之间，两座村庄之间的距离如果不超过的距离如果不超过d就可以用该型号的无线电收发机直接通讯，就可以用该型号的无线电收发机直接通讯，d值值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。直接通讯。现在有现在有k台（台（0 k 100）卫星设备，计算出应该如何分配）卫星设备，计算出应该如何分配这这k台卫星设备，才能

11、使所拥有的无线电收发机的台卫星设备，才能使所拥有的无线电收发机的d值最小，并保证每值最小，并保证每两座村庄之间都可以直接或间接地通讯。两座村庄之间都可以直接或间接地通讯。例例1：北极通讯网络：北极通讯网络第18页/共24页例如，对于下面三座村庄：例例1：北极通讯网络：北极通讯网络ABCA(10,10)B(10,0)C(30,0)第19页/共24页例例1：北极通讯网络：北极通讯网络 如果没有任何卫星设备或只有如果没有任何卫星设备或只有1 1台卫星设备（台卫星设备（k=0k=0或或k=1k=1），则满足条件的最小的），则满足条件的最小的d=20d=20，因为，因为A A和和B B，B B和和C C

12、可以用无线电直接通讯；而可以用无线电直接通讯；而A A和和C C可以用可以用B B中转实现间接通中转实现间接通讯（即消息从讯（即消息从A A传到传到B B，再从，再从B B传到传到C C）；）；如果有如果有2 2台卫星设备（台卫星设备（k=2k=2），则可以把这两台设备），则可以把这两台设备分别分配给分别分配给B B和和C C，这样最小的，这样最小的d d可取可取1010，因为，因为A A和和B B之间之间可以用无线电直接通讯；可以用无线电直接通讯；B B和和C C之间可以用卫星直接通讯；之间可以用卫星直接通讯；A A和和C C可以用可以用B B中转实现间接通讯。中转实现间接通讯。如果有如果有

13、3 3台卫星设备，则台卫星设备，则A,B,CA,B,C两两之间都可以直接两两之间都可以直接用卫星通讯，最小的用卫星通讯，最小的d d可取可取0 0。第20页/共24页知道卫星设备的数量，求最小的收发距离，可知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。把能比较困难；如果知道距离求数量，就很简单了。把所有可以互相通讯的村庄连接起来，构成一个图。卫所有可以互相通讯的村庄连接起来，构成一个图。卫星设备的台数就是图的连通支的个数。星设备的台数就是图的连通支的个数。问题转化为：找到一个最小的问题转化为：找到一个最小的d，使得把所有，使得把所有权值大于权值大于d的边去掉之后，连通支的个数小于等于的边去掉之后，连通支的个数小于等于k。例例1：北极通讯网络：北极通讯网络第21页/共24页定理定理2 2：如果去掉所有权值大于：如果去掉所有权值大于d d的边后，最小生成树被分的边后，最小生成树被分割成割成 为为k k个连通分支，图也被分割成为个连通分支，图也被分割成为k k个连通分支。个连通分支。得到构造算法得到构造算法：最小生成树的最小生成树的第第k长边长边就是问题的解。就是问题的解。例例1：北极通讯网络：北极通讯网络第22页/共24页TheEnd第23页/共24页感谢您的观看！第24页/共24页