《7.4最小生成树.ppt》由会员分享，可在线阅读，更多相关《7.4最小生成树.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.4 生成树与最小生成树生成树与最小生成树achdekfachkfed深度优先遍历次序深度优先遍历次序:achkfed知知 识识 回回 顾顾此图的生成树唯一吗？achdekfachkfed深度优先遍历次序深度优先遍历次序:achkfed广度优先遍历次序广度优先遍历次序:afedckh知知 识识 回回 顾顾achkfedachkfed深度优先生成树深度优先生成树广度优先生成树广度优先生成树知知 识识 回回 顾顾一个图可以有许多棵不同的生成树一个图可以有许多棵不同的生成树生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成
2、树有n-1条边条边7.4 生成树与最小生成树生成树与最小生成树7.4生成树与最小生成树生成树与最小生成树问题的提出：问题的提出：要在要在n个城市间建立通信联络网个城市间建立通信联络网，问怎么样铺设线路，问怎么样铺设线路能使总造价最底（设已知各城市之间是否可连接以及能使总造价最底（设已知各城市之间是否可连接以及相应的造价）。相应的造价）。1654327131791812752410顶点顶点表示城市表示城市边边表示两城市之间的线路表示两城市之间的线路权权城市间建立通信线路所城市间建立通信线路所需花费代价需花费代价1654327131791812752410问题分析问题分析n个城市间建立通信网，只需
3、个城市间建立通信网，只需n-1条线路条线路问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1条，能把条，能把 所有城市（顶点）均连起来，且总耗费所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小（各边权值之和）最小7.4生成树与最小生成树生成树与最小生成树 在一个连通网的所有生成树中，各边权值之和最在一个连通网的所有生成树中，各边权值之和最小的那棵生成树称为该连通网的小的那棵生成树称为该连通网的最小代价生成树最小代价生成树，简称为简称为最小生成树最小生成树。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）Kruskal该问题等价于：该问题等价于：算法一：（普里
4、姆算法）算法一：（普里姆算法）Prim 如何建立构造网的一棵如何建立构造网的一棵最小生成树最小生成树7.47.4生成树与最小生成树生成树与最小生成树一、一、Prim算法的基本思想算法的基本思想:取连通网中任意一个顶点取连通网中任意一个顶点 v0 作为生成树作为生成树的根，然后反复在的根，然后反复在一端已选，另一端未选一端已选，另一端未选的边中选择一条最小边，直到所有顶点都的边中选择一条最小边，直到所有顶点都在生成树上为止。在生成树上为止。UV-U7.47.4生成树与最小生成树生成树与最小生成树165432651356642513116314164314211643214251654321425
5、3136425二、二、Prim算法的实例算法的实例7.47.4生成树与最小生成树生成树与最小生成树abcdegf再例如再例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=677.47.4生成树与最小生成树生成树与最小生成树56313ae2dcbgf415adfgbce考虑如图：考虑如图：根据普里姆（根据普里姆（PrimPrim）算法，求它的最小生成树（以）算法，求它的最小生成树（以A A为顶点），得出算法的框架为顶点），得出算法的框架7.47.4生成树与最小生成树生成树与最小生成树n选取起始顶点；选取起始顶点；nfor(i
6、=1;i=n-1;i+)n从候选边中找出最小的边（从候选边中找出最小的边（V，VK）；）；n将将Vk设置为已选顶点；设置为已选顶点；n调整候选边集合；调整候选边集合；n三、三、Prim算法的实现算法的实现UV-U7.47.4生成树与最小生成树生成树与最小生成树costijWij ViVj且且(vi,vj)E(G)0 Vi=Vj 其它其它图用邻接矩阵表示图用邻接矩阵表示V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6三、三、Prim算法的实现算法的实现7.47.4生成树与最小生成树生成树与最小生成树n选取起始顶点
7、；选取起始顶点；nfor(i=1;i=n-1;i+)n从候选边中找出最小的边（从候选边中找出最小的边（V，VK）；）；n将将Vk设置为已选顶点；设置为已选顶点；n调整候选边集合；调整候选边集合；n三、三、Prim算法的实现算法的实现候选边如候选边如何记录？何记录？UV-U7.47.4生成树与最小生成树生成树与最小生成树ABCFEDJ三、三、Prim算法的实现算法的实现候选边为：每个未选顶点，到已选顶点的最小边。候选边为：每个未选顶点，到已选顶点的最小边。顶点顶点顶点顶点权值权值 UV-UABCDEFJ 0 1 2 3 4 5 6 0 1 2 3 4 5 6 viclosestlowcost顶点
8、v-u顶点u边的权值对每一顶点对每一顶点v vi V-U,在辅助数组中应包括两个量在辅助数组中应包括两个量,在在此用此用 ：存储该边依附的：存储该边依附的在在U中的顶点中的顶点 ：存储该边上的权存储该边上的权 数组数组closesti数组数组lowcosti7.47.4生成树与最小生成树生成树与最小生成树V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6如如 0 0 0 0 0 00 0 0 0 0 0 0 60 6 1 1 5 max 5 max maxmax viclosestlowcost 0 1 2 3
9、4 5U=v1U UV-U=v2,V3,V4,V5,V6 数组数组closesti数组数组lowcosti对每一顶点对每一顶点v vi V-U,在辅助数组中应包括两个量在辅助数组中应包括两个量,在在此用此用 ：存储该边依：存储该边依附的在附的在U中的顶点中的顶点 ：存储该边上的权存储该边上的权对于最小边的查找：变成了在对于最小边的查找：变成了在lowcostlowcost数组中查找最小值。数组中查找最小值。对于调整候选边集合：变成了连入新顶点后，对于调整候选边集合：变成了连入新顶点后，closestclosest数数组和组和lowcostlowcost数组的调整。数组的调整。7.47.4生成树
10、与最小生成树生成树与最小生成树三、三、Prim算法的实现算法的实现 0 0 0 0 0 00 0 0 0 0 0 0 60 6 0 0 5 max 5 max maxmax V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6例例 0 0 0 0 0 00 0 0 0 0 0 0 60 6 1 1 5 max 5 max maxmax viclosestlowcost 0 1 2 3 4 5 vi closestlowcost 0 1 2 3 4 5 0 2 0 0 2 20 2 0 0 2 2 0 5 0 5 6
11、0 5 0 5 6 4 4U=v1U=v1,v3V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 65 52 21 16 65 55 54 46 6U UU UV-U=v2,V3,V4,V5,V6 V-U=v2,V4,V5,V6 v1 v1 v1 v1 v1 v1v1 v1 v1 v1 v1 v1v3v3v35647.47.4生成树与最小生成树生成树与最小生成树 v1 v1 v1 v1 v1 v1 v1 v1 v1v1 v1v1 0 60 6 1 1 5 max max5 max max lowcostlowcostv1v1 v1 v3 v1 v1 v3 v3v
12、1 v3 v1 v1 v3 v3 0 5 0 5 60 5 0 5 6 4 4 closestlowcostlowcostv1,v3v1,v3 v1 v3 v1 v6 v3 v1 v3 v1 v6 v3 v3v3 0 5 00 5 0 2 2 6 6 0 0 closestlowcostlowcost v1,v3,v6v1,v3,v6 v1 v3 v1 v6 v3 v1 v3 v1 v6 v3 v3v3 0 0 5 5 0 0 6 0 0 6 0 0 closestlowcostlowcostv1,v3,v6,v4v1,v3,v6,v4 v1 v3 v1 v6 v2 v3v1 v3 v1 v6
13、 v2 v3 0 0 0 00 0 0 0 3 3 0 0 closestlowcostlowcostv1,v3,v6,v4,v2v1,v3,v6,v4,v2 v1 v3 v1 v6 v2 v3v1 v3 v1 v6 v2 v3 0 0 0 0 0 0 0 0 0 0 0 0 closestlowcostlowcostv1,v3,v6,v4,v2,v5v1,v3,v6,v4,v2,v5i iclosest 0 0 1 2 3 4 5 1 2 3 4 5 U Uclosedge v1 v2 v3 v4 v5 v6V V3 3V V1 1V V4 4V V6 6V V5 5V V2 23 36 6
14、5 52 21 16 65 55 54 46 67.47.4生成树与最小生成树生成树与最小生成树u算法描述算法描述(1)(1)初始化初始化(U=(U=V),closestiV),closesti=V;lowcostiV;lowcosti=costVicostVi;lowcostVlowcostV=0;(i=1,2,3,n-1;)=0;(i=1,2,3,n-1;)(2)(2)每次扫描数组每次扫描数组lowcostlowcost ，找出值最小且不为找出值最小且不为0 0的的lowcostklowcostk，得到最小生成树的一条边（得到最小生成树的一条边（closestk,kclosestk,k),
15、),将其输出。将其输出。（3 3）令）令lowcostklowcostk=0,=0,将将k k并入并入U U 中中（4 4）修改数组）修改数组closesticlosesti 和和 lowcostilowcosti（lowcostilowcosti！=0=0 及及i V-i V-U U）（5 5）重复（重复（2 2）（）（3 3）（）（4 4），直到），直到U=VU=V（或循环或循环 n-1 n-1 次）结束次）结束costijWij ViVj且且(vi,vj)E(G)0 Vi=Vj 其它其它u算法实现：图用邻接矩阵表示算法实现：图用邻接矩阵表示7.47.4生成树与最小生成树生成树与最小生成树
16、普里姆算法普里姆算法void PRIM(void PRIM(intint costN,costN,intint start_vstart_v,intint N)N)intint closestN,lowcostN,i,j,k,minclosestN,lowcostN,i,j,k,min;for(i=0;iN;i+)for(i=0;iN;i+)lowcostilowcosti=coststart_vicoststart_vi;closesticlosesti=start_vstart_v;for(i=1;iN;i+)/for(i=1;iN;i+)/循环循环n-1n-1次，每次求出最小生成树的一条
17、边次，每次求出最小生成树的一条边 min=MAX;min=MAX;for(j=0;jN;j+)for(j=0;jN;j+)if(if(lowcostjlowcostj!=0&!=0&lowcostjlowcostjmin)min)min=min=lowcostj;klowcostj;k=j;/=j;/找出值最小的找出值最小的 lowcostklowcostk printfprintf(“边（边（%d,%dd,%d）:%:%dndn”,closestk,k,closestk,k,lowcostklowcostk););lowcostklowcostk=0;/=0;/将将 k k 并入并入U U
18、中中 for(j=0;jN;j+)/for(j=0;jN;j+)/修改修改 lowcostlowcost 和和closest closest if(if(costkjcostkj lowcostjlowcostj)lowcostjlowcostj=costkj;closestjcostkj;closestj=k;=k;算法评价：算法评价：T(n)=O(n)7.47.4生成树与最小生成树生成树与最小生成树普里姆算法普里姆算法适应范围：稠密图适应范围：稠密图分析算法不难看出：分析算法不难看出：本节重点：掌握最小生成树的本节重点：掌握最小生成树的prim方法方法7.47.4生成树与最小生成树生成树与
19、最小生成树作业：五：考虑如图：作业：五：考虑如图：（1）从顶点）从顶点A出发，求它的深度优先生成树。出发，求它的深度优先生成树。（2）从顶点）从顶点E出发，求它的广度优先生成树。出发，求它的广度优先生成树。（3）根据普里姆（）根据普里姆（Prim）算法，求它的最小生成树（以）算法，求它的最小生成树（以A为顶点）。为顶点）。56313ae2dcbgf415考虑如图：考虑如图：（1）从顶点）从顶点A出发，求它的深度优先生成树。出发，求它的深度优先生成树。（2）从顶点）从顶点E出发，求它的广度优先生成树。出发，求它的广度优先生成树。（3）根据普里姆（）根据普里姆（Prim）算法，求它的最小生成树（以
20、）算法，求它的最小生成树（以A为顶点）为顶点）。aedcbgfaedcbgf作业：五：考虑如图：作业：五：考虑如图：（1）从顶点）从顶点A出发，求它的深度优先生成树。出发，求它的深度优先生成树。（2）从顶点）从顶点E出发，求它的广度优先生成树。出发，求它的广度优先生成树。（3）根据普里姆（）根据普里姆（Prim）算法，求它的最小生成树（以）算法，求它的最小生成树（以A为顶点）。为顶点）。56313ae2dcbgf415adfgbce具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，二、克鲁斯卡尔算法的基本思想：二、克鲁
21、斯卡尔算法的基本思想：具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。abcdegf195141827168213ae12dcbgf7148531621例如例如:712181927165432651356642516543
22、212345例如例如:例例165432651356645516543213455551.1.初始时，设无向连通网图初始时，设无向连通网图G=G=（V V，E E）的最小生成树初态为）的最小生成树初态为S=S=（V V，）。）。即即S S包含包含G G中所有中所有n n个顶点，它们各自构成单独的个顶点，它们各自构成单独的n n个连通分量，顶点间没有个连通分量，顶点间没有任何边存在。任何边存在。2.2.以图以图G G的边集合的边集合E E为基础，按照各边的权值，由小到大对它们进行挑选；为基础，按照各边的权值，由小到大对它们进行挑选；3.3.若选出的边的两个顶点分属若选出的边的两个顶点分属S S中两
23、个不同的连通分量，那就将其从中两个不同的连通分量，那就将其从E E中去除，中去除，用它将用它将S S中的那两个连通分量连成一个连通分量，成为最小生成树中的那两个连通分量连成一个连通分量，成为最小生成树S S中的一中的一个新连通分量；个新连通分量；4.4.如果挑选出来的边的两个顶点属于如果挑选出来的边的两个顶点属于S S中的同一个连通分量，那么就将其舍中的同一个连通分量，那么就将其舍弃，重新再挑选，以避免在弃，重新再挑选，以避免在S S里形成回路；里形成回路；5.5.不断实行（不断实行（2 2）（4 4）步，当）步，当S S里只剩有一个连通分量时，算法终止，该连里只剩有一个连通分量时，算法终止，
24、该连通分量即为所求的图通分量即为所求的图G G的最小生成树的最小生成树S S。1 2 3 4 5 61 0 7 9 2 0 5 63 7 5 0 1 24 1 0 25 9 0 16 6 2 2 1 0costu算法实现：图用邻接矩阵表示算法实现：图用邻接矩阵表示V19V5V3V4V2V67526121 2 3 4 5 61 0 7 9 2 0 5 63 7 5 0 1 24 1 0 25 9 0 16 6 2 2 1 0costvoid Sort(cost,n,ES)k=1;for(i=1;i=n;i+)for(j=1;j=n;j+)if(ij&costij!=0&costij!=32767
25、)ESk.vex1=i;ESk.vex2=j;ESk.weight=costij;k+;for(i=2;i=1&temp.weightESj.weight)ESj+1=ESj;j-;ESj+1=temp;kvex1vex2weight1 2 3 4 5 6 7 81 1 2 2 3 3 4 53 5 3 6 4 6 6 67 9 5 6 1 2 2 1ES初态：kvex1vex2weight1 2 3 4 5 6 7 8353422114666363511225679ES排序后：Sort()Sort()功能是基于图功能是基于图G G的邻接矩阵的邻接矩阵costcost，产生出，产生出排好序的边
26、集数组排好序的边集数组ESES，供主程序使用。，供主程序使用。void Kruskcostl_Mst(cost,ES,n)sort(cost,n,ES);for(i=1;i=n;i+)vseti=i;k=1;j=1;while(k=n-1)u1=ESj.vex1;u2=ESj.vex2;sn1=vsetu1;sn2=vsetu2;if(sn1!=sn2)printf(“(%d,%d):%d ”,u1,u2,ESj.weight);for(i=1;i=n;i+)if(vseti=sn2)vseti=sn1;k+;j+;初始时初始时顶点顶点子图子图 1 2 3 4 5 6 71 2 3 4 5 6
27、 7第一次第一次顶点顶点子图子图 1 2 3 4 5 6 71 2 3 3 5 6 7第二次第二次顶点顶点子图子图 1 2 3 4 5 6 71 2 3 3 5 5 7kvex1vex2weight1 2 3 4 5 6 7 83 5 3 4 2 2 1 14 6 6 6 3 6 3 51 1 2 2 5 6 7 9排序后的排序后的ES：void Kruskcostl_Mst(cost,ES,n)sort(cost,n,ES);for(i=1;i=n;i+)vseti=i;k=1;j=1;while(k=n-1)u1=ESj.vex1;u2=ESj.vex2;sn1=vsetu1;sn2=vs
28、etu2;if(sn1!=sn2)printf(“(%d,%d):%d ”,u1,u2,ESj.weight);for(i=1;i=n;i+)if(vseti=sn2)vseti=sn1;k+;j+;第二次第二次顶点顶点子图子图 1 2 3 4 5 6 71 2 3 3 5 5 7第三次第三次顶点顶点子图子图 1 2 3 4 5 6 71 2 3 3 3 3 7kvex1vex2weight1 2 3 4 5 6 7 83 5 3 4 2 2 1 14 6 6 6 3 6 3 51 1 2 2 5 6 7 9排序后的排序后的ES：void Kruskcostl_Mst(cost,ES,n)so
29、rt(cost,n,ES);for(i=1;i=n;i+)vseti=i;k=1;j=1;while(k=n-1)u1=ESj.vex1;u2=ESj.vex2;sn1=vsetu1;sn2=vsetu2;if(sn1!=sn2)printf(“(%d,%d):%d ”,u1,u2,ESj.weight);for(i=1;i=n;i+)if(vseti=sn2)vseti=sn1;k+;j+;第三次第三次顶点顶点子图子图 1 2 3 4 5 6 71 2 3 3 3 3 7第四次第四次顶点顶点子图子图 1 2 3 4 5 6 71 2 2222 7kvex1vex2weight1 2 3 4
30、5 6 7 83 5 3 4 2 2 1 14 6 6 6 3 6 3 51 1 2 2 5 6 7 9排序后的排序后的ES：kvex1vex2weight1 2 3 4 5 6 7 83 5 3 4 2 2 1 14 6 6 6 3 6 3 51 1 2 2 5 6 7 9排序后的排序后的ES：初始初始：1 2 3 4 5 6 第第1次次：1 2 3 3 5 6 第第2次次：1 2 3 3 5 5第第3次次：1 2 3 3 3 3 第第4次次：1 2 2 2 2 2 第第5次次：1 1 1 1 1 1 顶点顶点i：1 2 3 4 5 6 vseti的取值的取值普里姆算法普里姆算法适应范围：适应范围：稠密图稠密图克鲁斯卡尔算法克鲁斯卡尔算法适应范围：适应范围：稀疏图稀疏图分析两种算法不难看出：本节重点：掌握最小生成树的两种方法本节重点：掌握最小生成树的两种方法