数据结构南开大学.ppt

数据结构南开大学.ppt数据结构第7章图-:顶点v至v‘’之间有路径存在连通图:无向图图G的任意两点之间都是连通的,则称G是连通图。连通分量::极小连通子图。包含图的所有n个结点,但只含图的n-1条边。在生成树中添 加一条边之后,必定会形成回路或环。因为在生成树的任意两点之间,本来就 是连通的,添加一条变之后,形成了这两点之间的第二条通路。ABCDEHMABCDEHM无向图G无向图G的生成树生成方法:进行深度为主的遍历或广度为主的遍历,得到深度优先生成树或广度优先生 成树。生成森林:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深度优先生成树或广度优先生成树。称之为生成森林。:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深度优先生成树或广度优先生成树。称之为生成森林。。(简称:最小生成树)MinimumCostSpanningTree定义:生成树中边的权值(代价)之和最小的树。实例:1243566165556342**********左图的最小代价生成树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‘是树的理由:连通且无回路。uvu’v’