11《数据结构》第七章(下).pdf

数据结构 北京邮电大学信息安全中心 武斌 上次课内容 上次课 （图(上) ）内容： 领会图的类型定义。 熟悉图的各种存储结构及其构造算法，了解各种存 储结构的特点及其选用原则。 熟练掌握图的两种遍历算法。 2 本次课程学习目标 学习完本次课程，您应该能够： 掌握无向网的最小生成树方法。 理解有向无环图及其应用。 领会最短路径、拓扑排序、关键路径。 理解各种图的应用问题的算法。 3 图的连通性问题 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题（二） 7.5 有向无环图及其应用 7.6 最短路径 4 最小生成树 最小生成树(Minimum Cost Spanning Tree)：生成树中边的权 值（代价）之和最小的树。 实例： 左图的最小代价生成树 1 1 5 6 1 1 2 5 3 5 4 2 5 3 4 3 6 4 2 3 4 2 5 6 6 5 6 最小生成树 MST 性质：  假设G = {V, { E } } 是一个连通图，U 是结点集合V 的一 个非空子集。若( u, v ) 是一条代价最小的边，且u 属于U , v 属于V-U，则必存在一棵包括边 ( u, v ) 在内的最小代 价生成树。 普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST 性质构造最小生成树的算法。 6 最小生成树 MST 性质证明 （反证法）： 1. 假定存在一棵不包括边 ( u, v ) 在内的最小代价生成树，设其为T 。 2. 将边( u, v ) 添加到树T ，则形成一条包含 ( u, v ) 的回路。 3. 因此，必定存在另一条边 ( u,v) ，且u 属于U , v属于V - U 。删去边 ( u,v) ，得到另一棵生成树T ; 因为边( u, v ) 的代价小于边 ( u ,v) 的代 价，所以新的生成树T 将是代价最小的树。 4. 和原假设矛盾。 T