(19)--第5章 图-最小生成树数据结构.ppt

《(19)--第5章 图-最小生成树数据结构.ppt》由会员分享，可在线阅读，更多相关《(19)--第5章 图-最小生成树数据结构.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 图图最小生成树最小生成树的定义普里姆算法1 12 2教学内容教学内容克鲁斯卡尔算法3 3极小连通子图极小连通子图极小连通子图极小连通子图：该子图是该子图是G G 的连通子图，在该子图中删除任的连通子图，在该子图中删除任何一条边，子图不再连通。何一条边，子图不再连通。生成树：生成树：生成树：生成树：包含图包含图G G所有顶点的极小连通子图（所有顶点的极小连通子图（n-1条边）条边）。G1G1的生成树的生成树连通图连通图 G1G1 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V4V4 V3V3 V1V1 V2V2最小

2、生成树最小生成树欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；条线路；但因为每条线路都会有对应的经济成本，而但因为每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-1)/2 n(n-1)/2 条线路，那么，如何选择条线路，那么，如何选择n n1 1条线路，使总费用条线路，使总费用最少？最少？数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n n1 1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n n个城市间通信网。个城市间通信网。显

3、然此连通网显然此连通网是一个是一个生成树生成树！最小生成树的典型用途最小生成树的典型用途PTA题目n公路村村通n畅通工程之最低成本建设问题n畅通工程之局部最小花费问题求最小生成树求最小生成树首先明确首先明确：使用不同的遍历图的方法，可以得到不同的生成树使用不同的遍历图的方法，可以得到不同的生成树从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树个顶点的连通网络的生成树有有 n n 个顶点、个顶点、n-n-1 1 条边。条边。目标：目标：在网的多个生成树中，寻找一个各边在网的多个生成树中，寻找一

4、个各边权值之和最小权值之和最小的生成树的生成树任何一个带权无向连通图的最小生成树（）。是唯一的是不唯一的有可能不唯一有可能不存在ABCD提交单选题2分v必须只使用该必须只使用该网中的边网中的边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n-1n-1条边来联结网络中的条边来联结网络中的n n个个顶点顶点v不能使用产生不能使用产生回路回路的边的边构造最小生成树的准则构造最小生成树的准则vPrimPrim（普里姆）算法（普里姆）算法 vKruskalKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法PrimPrim算法算法:归并顶点归并顶点，与边数无关，适于，与边数无关，适

5、于稠密网稠密网Kruskal算法：算法：归并边归并边，适于，适于稀疏网稀疏网如何求最小生成树如何求最小生成树最小生成树的重要性质如下：最小生成树的重要性质如下：设设N=(V,E)是一连通网，是一连通网，U 是顶点集是顶点集V的一个非空子集。若（的一个非空子集。若（u,v）是一条具）是一条具有最小权值的边，其中有最小权值的边，其中uU，vV-U，则存在一棵包含边（，则存在一棵包含边（u,v）的最小生）的最小生成树。成树。用反证法来证明这个最小生成树用反证法来证明这个最小生成树（MST）的性质：）的性质：假设不存在这样一棵包含边（假设不存在这样一棵包含边（u,v）的最小生成）的最小生成树。任取一棵

6、最小生成树树。任取一棵最小生成树T，将（，将（u,v）加入）加入T中。根中。根据树的性质，此时据树的性质，此时T中必形成一个包含（中必形成一个包含（u,v）的回）的回路，且回路中必有一条边（路，且回路中必有一条边（u,v）的权值大于或等）的权值大于或等于（于（u,v）的权值。删除（）的权值。删除（u,v），则得到一棵代），则得到一棵代价小于等于价小于等于T的生成树的生成树T，且，且T为一棵包含边（为一棵包含边（u,v）的最小生成树。这与假设矛盾。）的最小生成树。这与假设矛盾。设连通网络设连通网络 N=V,E 1.1.从从从从某某某某顶顶顶顶点点点点 u u0 0 出出出出发发发发，选选选选择择

7、择择与与与与它它它它关关关关联联联联的的的的具具具具有有有有最最最最小小小小权权权权值值值值的的的的边边边边(u u0 0,v v)，将将将将其其其其顶顶顶顶点点点点加加加加入入入入到到到到生生成成树树的的顶顶点点集集合合U中中中中2.2.每每每每一一一一步步步步从从从从一一一一个个个个顶顶顶顶点点点点在在在在U U中中中中，而而而而另另另另一一一一个个个个顶顶顶顶点点点点不不不不在在在在U U中中中中的的的的各各各各条条条条边边边边中中中中选选选选择择择择权权权权值值值值最最最最小小小小的的的的边边边边(u,(u,v),v),把把把把它它它它的的的的顶顶顶顶点点点点加入到加入到加入到加入到U

8、中中中中3.3.直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合直到所有顶点都加入到生成树顶点集合U U中为止中为止中为止中为止普里姆算法的基本思想普里姆算法的基本思想归并顶点归并顶点应用普里姆算法构造最小生成树的过程应用普里姆算法构造最小生成树的过程下列网其最小生成树的总权重是。10321716ABCD提交单选题2分 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中集中的每个顶点，记录和顶点集的每个顶点，记录和顶点集U中顶点相连中顶点相连接的代价最小的边：接的代价最小的边：typedef struct VertexType adj

9、vex;/U集中的顶点序号集中的顶点序号 VRType lowcost;/边的权值边的权值 closedgeMAX_VERTEX_NUM;abcdegf195141827168213ae12dcb7aaa19141814e12ee8168d3dd7213c5 5设连通网络设连通网络 N=V,E 1.构构造造一一个个只只有有 n 个个顶顶点点，没没有有边边的的非非连连通通图图 T=V,每个顶点自成一个连通分量每个顶点自成一个连通分量2.在在 E 中中选选最最小小权权值值的的边边,若若该该边边的的两两个个顶顶点点落落在在不不同同的的连连通通分分量量上上，则则加加入入 T 中中；否否则则舍舍去去，重

10、新选择重新选择3.重重复复下下去去，直直到到所所有有顶顶点点在在同同一一连连通通分分量量上上为止为止克鲁斯卡尔算法的基本思想克鲁斯卡尔算法的基本思想归并边归并边应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。正确错误AB提交单选题1分算法描述算法描述:构造非连通图构造非连通图 ST=(V,);k=i=0;/k 计选中的边数计选中的边数 while(kn-1)+i;检查边集检查边集 E 中第中第 i 条权值最小的边条权值最小的边(u,v);若若(u,v)加入加入ST后不使后不使ST中产生回路，中产生回路，则

11、则 输出边输出边(u,v);且且 k+;算法要解决的关键问题1.边的排序问题？优先队列2.如何判断加入一条边后是否出现回路？并查集对于下列的网，使用克鲁斯卡尔算法求最小生成树，依次得到的边集是。（A，D），（B，C），（E，A），（C，E）（A，D），（D，E），（B，C），（C，E）（A，D），（D，E），（E，C），（C，B）（A，D），（A，B），（A，E），（E，C）ABCD提交单选题2分给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：8152022ABCD提交单选题2分总结1.最小生成树：权值之和最小的生成树2.普里姆算法：贪心算法加点法3.克鲁斯卡尔算法权值递增贪心算法加边法