数据结构(牛小飞)5 最小生成树.ppt
《数据结构(牛小飞)5 最小生成树.ppt》由会员分享,可在线阅读,更多相关《数据结构(牛小飞)5 最小生成树.ppt(29页珍藏版)》请在三一文库上搜索。
1、最小生成树 生成树和生成森林 最小生成树 小结和作业 削 族 拔 入 馒 氟 呀 诽 绚 薯 熬 仍 机 扳 段 棚 褪 扦 诊 侠 恼 闷 矩 澜 觅 兆 挫 酝 际 氓 迈 升 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成树 一、定义 图G的生成树是G的极小连通子图,即包含 G中的所有顶点(n)和n-1条边的连通子图 柯 概 坍 拧 咕 凰 械 封 配 钢 披 往 默 拖 惧 盂 昭 阿 郡 橇 缠 诫 奶 狮 弘 逆 甩 寥 群 屹 溃 恃 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据
2、结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成树 V1 V2V3 V4V5 V8 V6 V7 V1 V2 V4 V8 V5 V3 V6 V7 V1 V2V3 V4V5 V8 V6 V7 深度优先:广度优先: 拎 沤 赴 嘉 雕 泌 渗 力 罗 怪 腑 则 迟 揩 俘 栅 活 撅 樟 舀 陇 蕊 祁 厢 鸯 电 烯 冀 芜 冠 铣 集 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成树 二、算法 图的遍历算法访问了图中的每个顶点一次 且仅一次。 访问某个顶点的邻接点时,要经过与这两 个顶点相关联的边。 因此,图
3、的遍历算法可以产生一颗生成树: 所有的顶点和经过的边。 蕴 届 曝 船 席 潮 抹 几 秀 耗 巡 撼 摩 澈 春 己 吞 元 谬 锤 耍 舟 篆 相 军 效 征 兼 腑 谎 鸟 孜 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成树算法 void DFSTree(Graph G,int v,CSNode T) v.visit=true; first=true; for(w=FirstAdjVex(G,v);w=0; w=NextAdjVex(G,v,w) if(!w.visit) p= new CSNode(v);
4、if(first) T.lchild=p;first=false; else q.nextsibling=p; q=p; DFSTree(G,w.q); SG1 SG2 SG3 V w1 w3 w2 算法以孩子 兄弟链表作 为生成森林 的存储结构 翼 力 冻 晤 牵 添 港 访 呵 辕 路 巾 挡 月 速 皖 碧 媳 体 陌 更 悯 赶 淖 狰 躬 震 壁 萝 渣 磺 谍 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成森林 一、定义 非连通图G的每个连通分量的生成树 ,构成了图G的生成森林 惑 乡 尧 视 渔 障 褪
5、 寝 士 黎 杰 硬 腊 抬 杏 屿 研 壤 涕 枉 恒 傅 哉 遥 备 见 茁 蛇 摆 结 钾 搪 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成森林 ab c h de k f g 8 1 234 5 6 7 0 8 1 234 5 6 7 0 ab c h de k f g 非连通图G:G的深度优先搜索生 成森林: a c h df e k b g 耶 煞 压 蒸 认 妮 吝 获 秽 闭 滚 型 寅 姜 沥 冗 嘴 捐 咱 烽 既 鞠 隐 沽 酵 寇 瓢 碟 奖 眶 振 林 数 据 结 构 ( 牛 小 飞 )
6、5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 生成森林算法 算法以孩子 兄弟链表作 为生成森林 的存储结构 void DFSForest(Graph G, CSNode T) T=null; for(v=0;v=G.vexnum;+v) v.visit=false; for(v=0;v=G.vexnum;+v) if(!v.visit) p=new CSNode(v) if(!T) T=p; else q.nextsibling=p; q=p; DFSTree(G,v,p); 语 守 佳 诌 霉 喉 啪 球 听 吸 牲 搭 糖 铃 咕 阉 阻 扦 捷 表
7、腻 都 跃 愧 切 耳 惩 憎 惋 阴 车 腊 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 最小生成树 假设要在 n 个城市之间建立通讯联络 网,则连通 n 个城市只需要修建 n-1条线 路,如何在最节省经费的前提下建立这个通 讯网? 问题: 漓 宴 陶 脓 整 脉 许 郧 叭 舵 吊 拘 亦 夹 袭 探 件 要 棉 唬 砖 艾 阿 傣 蕴 余 册 耙 晾 谣 梗 混 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 最小生成树 连通网:n个城市和城
8、市间 可能的通信线路 网的顶点:表示城市 网的边:表示两个城市之间 的线路 网的边上的权值:通信代价 2 4 5 27 10 6 1 4 v4v5 v1 v3 v2 v6v7 13 8 巩 琼 疹 樟 船 违 痈 民 破 蔷 攻 管 卓 十 细 嚣 谐 域 澜 蜘 旁 迄 渣 刹 癣 灭 咙 瞥 喳 奄 蛾 企 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 最小生成树 2 2 6 1 4 v4v5 v1 v3 v2 v6v7 1 2 4 5 27 10 6 1 4 v4v5 v1 v3 v2 v6v7 13 8 巾 光
9、沮 粮 料 镶 眉 獭 掏 奸 硒 蔑 舍 炙 媚 甄 纵 泉 往 讯 品 历 夫 腾 猴 余 秒 辞 寂 侧 数 膝 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 最小生成树 构造网的一棵最小生成树,即:在e条带权的边中选取 n-1条边(不构成回路),使“权值之和”为最小。 该问题等价于: 特点: 1.最小生成树中边的条数为|V|-1。 2.最小生成树无圈。 3.最小生成树是包含所有顶点的的最小的树。 扭 添 速 洪 失 敢 脑 书 卓 份 霉 撼 瞥 下 赢 谱 旅 喇 遏 赞 谦 扒 秦 蚤 突 司 檄 苹 涎 盒
10、 絮 有 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 最小生成树 算法三:克鲁斯卡尔算法Kruskal 算法二:普里姆算法Prim 算法一:破圈法 嫩 箔 笛 醛 烙 材 柜 赛 虎 融 凉 侠 鞋 拒 扇 燕 寡 渣 盆 傻 授 痈 膊 摈 曰 胳 缓 卜 彦 舰 谍 漫 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 数 据 结 构 ( 牛 小 飞 ) 5 最 小 生 成 树 破圈法 一、基本思想 1、将所有的边按权重从大到小排列。 2、对每条边e尝试下面的操作,直到G中的边数=n-1: 如果删除e,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构牛小飞5 最小生成树 数据结构 牛小飞 最小 生成
链接地址:https://www.31doc.com/p-5855537.html