84最小生成树普里姆算法

z8.4 最小生成树 普里姆算法Data structures2引例公园导游图设计功能要求:了解公园所有景点 游客从公园大门进入，选一条游览各景点的线路。从一景点到另一景点的最短路径 各景点修建管道，总长度最短Data structures3怎样求得游览各景点的线路？(第12课时)2Data structures公园导游图需完成的功能:如何存储地图？(第11课时)1（注：分5次课依次完成该案例）3 如何求两点间的最短路径?(第13课时)4 求得管道修建方案?(第14、15课时)Data structures4思考:管道修建要解决的主要问题?如何铺设管道？3怎样保证总代价最小？2如何连通所有景点？1Data structures5问题1：连通所有景点ABCEFDGABCEFDGABCEFDG生成树：连通图的极小连通子图，含图中所有n个顶点，只有n-1条边。图a图b图c生成树不唯一Data structures6问题2：保证总代价最小ABCEFDG图aABCEFDG505040302025 图bABCEFDG504030202025图c最小生成树:图的所有生成树中,所有边上的权值之和最小的生成树。5050404020202530Data structures7vPrim（普里姆）算法 vKruskal（克鲁斯卡尔）算法最小生成树两种算法：问题2：保证总代价最小Data structures8 普里姆(Prim)算法思想：1.将图G=(V,E)分为两个顶点集 U：已选顶点集;V-U：未选顶点集.2.每次从V-U中选择一个到U中顶点距离最短的顶点;直到所有顶点都被选择.0543216513566425时间复杂度为o(n2)，n:顶点数 UV-U问题2：保证总代价最小Data structures91.普里姆(Prim)算法054321651UV-U012345构造过程0543216513566425图aData structures101.普里姆(Prim)算法054321651V-U134525645构造过程U0543216513566425图a0贪心思想Data structures111.普里姆(Prim)算法054321651UV-U0152564562构造过程0543216513566425图a34贪心思想Data structures121.普里姆(Prim)算法054321651UV-U01532564562构造过程0543216513566425图a4贪心思想Data structures131.普里姆(Prim)算法054321651UV-U015325645623构造过程0543216513566425图a4贪心思想Data structures141.普里姆(Prim)算法054321651UV-U015342564562305432115423构造过程0543216513566425图a贪心思想Data structures152.最小生成树应用管道最短问题转化为：能连通所有景点（顶点），且总距离最小的最小生成树。公园管道设计给各景点修建自来水管道，总长度最短Data structures16问题3：管道修建方案采用普里姆算法求得管道修建方案Data structures173.编程实现在VC中编程，采用prim算法求得自来水管道修建的方案。下一节将分析prim算法Data structures18504613228102514241618120410255图a3212614课堂练习1161661411604102531252(1)(2)Data structures19生成树：连通图中各顶点且无回路1最小生成树：总代价最小2普里姆(Prim)算法 (重点、难点)3课堂小结Data structures20课后实践8个小组：实现校园导游系统功能如下：查询各景点的相关信息；查询图中任意两个景点间的最短路径查询图中任意两个景点间的所有路径查询游览景点的最佳线路Data structures21Data structures课程中心:自主学习&资料下载Data structures22其他学习资源