图的生成树汇总课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《图的生成树汇总课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生成 汇总 课件
- 资源描述:
-
1、第十四讲第十四讲 图的生成树图的生成树第1页,共29页。主要内容2.Prim算法算法3.Kruskal算法算法第2页,共29页。要想判定一个无向图是否为连通图,或有几个连通分量,通要想判定一个无向图是否为连通图,或有几个连通分量,通过对无向图遍历即可得到结果。过对无向图遍历即可得到结果。非连通图:需从多个顶点出发进行搜索,而每一次非连通图:需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。访问序列恰为其各个连通分量中的顶点集。连通图:仅需从图中任一顶点出发,进行深度优连通图:仅需从图中
2、任一顶点出发,进行深度优先搜索(或广度优先搜索),便可访问到图中所有先搜索(或广度优先搜索),便可访问到图中所有顶点。顶点。无向图的连通性第3页,共29页。count=0;2.for(图中每个顶点图中每个顶点v)2.1 if(v尚未被访问过尚未被访问过)2.1.1 count+;2.1.2 从从v出发遍历该图;出发遍历该图;3.if(count=1)printf(图是连通的图是连通的“);else printf(图中有图中有count个连通分量个连通分量);求无向图的连通分量求无向图的连通分量无向图的连通性第4页,共29页。从某顶点出发进行深度优先遍历,并按其所有邻接点都从某顶点出发进行深度优
3、先遍历,并按其所有邻接点都访问(即出栈)的顺序将顶点排列起来。访问(即出栈)的顺序将顶点排列起来。从最后完成访问的顶点出发,沿着以该顶点为头的弧作逆从最后完成访问的顶点出发,沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点,则从余下的顶向的深度优先遍历。若不能访问到所有顶点,则从余下的顶点中最后访问的那个顶点出发,继续作逆向的深度优先遍历,点中最后访问的那个顶点出发,继续作逆向的深度优先遍历,直至有向图中所有顶点都被访问到为止。直至有向图中所有顶点都被访问到为止。每一次逆向深度优先遍历所访问到的顶点集便是该每一次逆向深度优先遍历所访问到的顶点集便是该有向图的一个强连通分量的顶点集
4、。有向图的一个强连通分量的顶点集。有向图的连通性第5页,共29页。(a)深度优先生成树)深度优先生成树 (b)广度优先生成树广度优先生成树V1V3V2V4V5V6V7V8V1V3V2V4V5V6V7V8图的生成树第6页,共29页。由深度优先遍历得到的为深度优先生成树,由深度优先遍历得到的为深度优先生成树,由广度优先遍历得到的为广度优先生成树。由广度优先遍历得到的为广度优先生成树。一个连通图的生成树可能不唯一,由不同的遍一个连通图的生成树可能不唯一,由不同的遍历次序、从不同顶点出发进行遍历都会得到不同历次序、从不同顶点出发进行遍历都会得到不同的生成树。的生成树。对于非连通图,通过图的遍历,将得到
5、的是生成森对于非连通图,通过图的遍历,将得到的是生成森林。林。结论:结论:图的生成树第7页,共29页。生成树的代价:生成树的代价:设设G=(V,E)是一个无向连通网,生成)是一个无向连通网,生成树上各边的权值之和称为该树上各边的权值之和称为该生成树的代价生成树的代价。最小生成树最小生成树(Minimum Spanning Tree,MST):在图在图G所有生所有生成树中,代价最小的生成树称为成树中,代价最小的生成树称为最小生成树最小生成树。最小生成树的概念可以应用到许多实际问题中。最小生成树的概念可以应用到许多实际问题中。例:在例:在n个城市之间建造通信网络,至少要架设个城市之间建造通信网络,
6、至少要架设n-1条通信条通信线路,而每两个城市之间架设通信线路的造价是不一样的,线路,而每两个城市之间架设通信线路的造价是不一样的,那么如何设计才能使得总造价最小?那么如何设计才能使得总造价最小?最小生成树第8页,共29页。假设假设G=(V,E)是一个无向连通网,是一个无向连通网,U是顶点集是顶点集V的一个非空的一个非空子集。若子集。若(u,v)是一条具有最小权值的边,其中是一条具有最小权值的边,其中uU,vVU,则必存在一棵包含边,则必存在一棵包含边(u,v)的最小生成树。的最小生成树。顶顶点点集集UVUuvvu顶顶点点集集T1T2最小生成树性质第9页,共29页。主要内容1.图的连通性图的连
7、通性3.Kruskal算法算法第10页,共29页。基本思想基本思想:设:设G=(V,E)是具有是具有n个顶点的连通网,个顶点的连通网,T=(U,TE)是是G的最小生成树,的最小生成树,T的的初始状态初始状态为为U=u0(u0V),),TE=,重复执行下述操作:在所有,重复执行下述操作:在所有uU,vV-U的边中找一条代价最小的边的边中找一条代价最小的边(u,v)并入集合并入集合TE,同时同时v并入并入U,直至,直至U=V。关键关键:是如何找到连接是如何找到连接U和和V-U的最短边。的最短边。利用利用MST性质,可以用下述方法构造候选最短边集:对应性质,可以用下述方法构造候选最短边集:对应V-U
8、中的每个顶点,保留从该顶点到中的每个顶点,保留从该顶点到U中的各顶点的最短边。中的各顶点的最短边。普里姆(Prim)算法第11页,共29页。U=A V-U=B,C,D,E,Fcost=(A,B)34,(A,C)46,(A,D),(A,E),(A,F)19 251234192646381725ABEDCF普里姆(Prim)算法第12页,共29页。251234192646381725ABEDCFU=A,F V-U=B,C,D,Ecost=(A,B)34,(F,C)25,(F,D)25,(F,E)26 普里姆(Prim)算法第13页,共29页。251234192646381725ABEDCFU=A,
展开阅读全文