数据结构 - 南开大学.ppt

数据结构数据结构第第7 7章章图图- 2 - 2 第第7 7章章图图 图的定义和术语图的定义和术语 图的存储结构图的存储结构 图的遍历图的遍历 图的连通性问题图的连通性问题 有向无环图及其应用有向无环图及其应用 最短路经最短路经 图的连通性问题图的连通性问题 无向图的连同分量和生成树无向图的连同分量和生成树 有向图的强连同分量有向图的强连同分量 最小生成树最小生成树 关节点和重连同分量关节点和重连同分量 无向图的连同分量和生成树无向图的连同分量和生成树 AB CD EFGIJL HM K AB CD EHM FGIJLK 无向图 G的三个连通分量无向图 G ?连通:顶点 v至v ‘’之间有路径存在?连通图:无向图图 G 的任意两点之间都是连通的,则称 G 是连通图。?连通分量:极大连通子图 无向图的连同分量和生成树无向图的连同分量和生成树?生成树:极小连通子图。包含图的所有 n 个结点,但只含图的 n-1 条边。在生成树中添加一条边之后,必定会形成回路或环。因为在生成树的任意两点之间,本来就是连通的,添加一条变之后,形成了这两点之间的第二条通路。 AB CD EHM AB CD EHM 无向图 G 无向图 G的生成树?生成方法:进行深度为主的遍历或广度为主的遍历,得到深度优先生成树或广度优先生成树。?生成森林:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深度优先生成树或广度优先生成树。称之为生成森林。 无向图的连同分量和生成树无向图的连同分量和生成树?生成森林:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深度优先生成树或广度优先生成树。称之为生成森林。 AB CD EFGIJL HM K AB CD EHM FGIJLK 无向图 G的生成森林无向图 G 有向图的强连同分量有向图的强连同分量??深度优先搜索是求有向图的强连同分量的深度优先搜索是求有向图的强连同分量的一个有效方法。一个有效方法。 最小生成树最小生成树最小代价生成树(简称:最小生成树) 最小代价生成树(简称:最小生成树) Minimum Cost Spanning Tree Minimum Cost Spanning Tree ?定义:生成树中边的权值(代价)之和最小的树。?实例: 124356 616 55563 42 124356 153 42 左图的最小代价生成树? MST 性质: 假设 G = {V, { E } } 是一个连通图, U 是结点集合 V 的一个非空子集。若 ( u, v ) 是一条代价最小的边,且 u 属于 U , v 属于 V - U ,则必存在一棵包括边 ( u, v ) 在内的最小代价生成树。 最小生成树最小生成树证明:假定存在一棵不包括边 ( u, v ) 在内的最小代价生成树,设其为 T。将边( u, v ) 添加到树 T ,则形成一条包含 ( u, v ) 的回路。因此,必定存在另一条边 ( u‘,v‘ ) ,且u’属于 U , v ‘属于 V - U 。删去边 ( u‘,v‘ ) ,得到另一棵生成树 T ‘ ; 因为边 ( u, v ) 的代价小于边 ( u‘,v‘ ) 的代价,所以新的生成树 T ‘将是代价最小的树。和原假设矛盾。新的生成树 T‘是树的理由:连通且无回路。 u v u’ v’ T 最小生成树最小生成树? Kruscal 算法 124356 616 55563 42最小代价生成树 124356 153 42 55