z 8.4 最小生成树 普里姆算法 2015年年 11月月 Data structures 2 引例 公园导游图设计 功能要求 : 了解公园所有景点 游客从公园大门进入，选一条 游览 各 景点 的线路。 从一景点到另一景点 的 最短路径 各景点修建管道，总长度最短 Data structures 3 怎样求得 游览 各 景点 的线路？ (第 12课时 ) 2 公园导游图需完成的功能 : 如何存储地图？ (第 11课时 ) 1 （注：分 5次课依次完成该案例） 3 如何求两点间的最短路径 ?(第 13课时 ) 4 求得管道修建方案 ?(第 14、 15课时 ) Data structures 4 思考 :管道修建要解决的主要问题 ? 如何铺设管道？3 怎样保证总代价最小？2 如何连通所有景点？1 Data structures 5 问题 1：连通所有景点 A B C E F D G A B C E F D G A B C E F D G 生成树： 连通图的极小连通子图， 含图中所有 n个顶点，只有 n-1条边。 图 a 图 b 图 c 生成树不唯一 Data structures 6 问
