§8.4最小生成树—普里姆算法.ppt

《§8.4最小生成树—普里姆算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、§8.4最小生成树—普里姆算法2015年11月引例公园导游图设计功能要求:了解公园所有景点游客从公园大门进入，选一条游览各景点的线路。从一景点到另一景点的最短路径各景点修建管道，总长度最短怎样求得游览各景点的线路？(第12课时)2Datastructures公园导游图需完成的功能:如何存储地图？(第11课时)1（注：分5次课依次完成该案例）3如何求两点间的最短路径?(第13课时)4求得管道修建方案?(第14、15课时)思考:管道修建要解决的主要问题?如何铺设管道？3怎样保证总代价最小？2如何连通所有景点？1问题

2、1：连通所有景点ABCEFDGABCEFDGABCEFDG生成树：连通图的极小连通子图，含图中所有n个顶点，只有n-1条边。图a图b图c生成树不唯一问题2：保证总代价最小ABCEFDG图aABCEFDG505040302025图bABCEFDG504030202025图c最小生成树:图的所有生成树中,所有边上的权值之和最小的生成树。5050404020202530Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法最小生成树两种算法：问题2：保证总代价最小普里姆(Prim)算法思想：1.将图G=(V,E)分为

3、两个顶点集U：已选顶点集;V-U：未选顶点集.2.每次从V-U中选择一个到U中顶点距离最短的顶点;直到所有顶点都被选择.0543216513566425时间复杂度为o(n2)，n:顶点数UV-U问题2：保证总代价最小1.普里姆(Prim)算法054321651UV-U012345构造过程0543216513566425图a1.普里姆(Prim)算法054321651V-U134525645构造过程U0543216513566425图a0贪心思想1.普里姆(Prim)算法054321651UV-U01525645

4、62构造过程0543216513566425图a34贪心思想1.普里姆(Prim)算法054321651UV-U01532564562构造过程0543216513566425图a4贪心思想1.普里姆(Prim)算法054321651UV-U015325645623构造过程0543216513566425图a4贪心思想1.普里姆(Prim)算法054321651UV-U015342564562305432115423构造过程0543216513566425图a贪心思想2.最小生成树应用管道最短问题转化为：能连通所

5、有景点（顶点），且总距离最小的最小生成树。公园管道设计给各景点修建自来水管道，总长度最短问题3：管道修建方案采用普里姆算法求得管道修建方案3.编程实现在VC中编程，采用prim算法求得自来水管道修建的方案。下一节将分析prim算法…504613228102514241618120410255图a3212614课堂练习2020116166141160410253122052(1)(2)生成树：连通图中各顶点且无回路1最小生成树：总代价最小2普里姆(Prim)算法(重点、难点)3课堂小结课后实践8个小组：实现校园

6、导游系统功能如下：查询各景点的相关信息；查询图中任意两个景点间的最短路径查询图中任意两个景点间的所有路径查询游览景点的最佳线路Datastructures课程中心:自主学习&资料下载其他学习资源谢谢各位专家指导！