图的最小生成树.ppt
《图的最小生成树.ppt》由会员分享,可在线阅读,更多相关《图的最小生成树.ppt(22页珍藏版)》请在三一办公上搜索。
1、第五章 图,5.4 图的最小生成树难点:生成树概念的理解重点:普里姆算法、克鲁斯卡尔算法,图的生成树,设无向连通图G=(V,E),其子图G=(V,T)满足:V(G)=V(G)n个顶点 G是连通的 G中无回路则G是G的生成树判断是否是生成树:具有n个顶点的无向连通图G()必然包括n个顶点()含n-1条边()无回路/连通,无向连通图的生成树举例,举例:有如下无向连通图,A,C,B,E,D,F,图G,思考题:,判断下列说法是否正确(1)图的生成树是唯一的。(2)在有n个顶点的无向图中,有n-1 条边的图一定是生成树。,深度优先生成树和广度优先生成树P81,根据深度和广度优先搜索法进行遍历就可以得到两
2、种不同的生成树,并分别称为深度优先生成树和广度优先生成树。,V0,以V0为起始点,深度优先遍历,深度优先生成树,广度优先生成树,网络的最小生成树P82,在一个图的每条边或弧上,有时可以标上具有某种含义的数值,这种边或弧上带权的图称为网(Network)。,如果连通图是一个网络,称该网络中所有生成树中权值总和最小的生成树为最小生成树(也称最小代价生成树)。,例如:铺设煤气管道问题(图形结构)假设要在某个城市的n个居民区之间铺设煤气管道,则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道,管道铺设方案。在众多可选边中,如何选择n-1条边,使总代价最小?这就是求该网络
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 生成

链接地址:https://www.31ppt.com/p-6257736.html