电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

数据结构(牛小飞)5最小生成树

29页
  • 卖家[上传人]:cn****1
  • 文档编号:591455822
  • 上传时间:2024-09-17
  • 文档格式:PPT
  • 文档大小:361KB
  • 数据结构(牛小飞)5最小生成树_第1页
    数据结构(牛小飞)5最小生成树_第2页
    数据结构(牛小飞)5最小生成树_第3页
    / 29 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、最小生成树生成树和生成森林最小生成树小结和作业生成树一、定义一、定义图图G的生成树是的生成树是G的极小连通子图,即包含的极小连通子图,即包含G中的所有顶点(中的所有顶点(n)和)和n-1条边的连通子图条边的连通子图生成树V1V2V3V4V5V8V6V7V1V2V4V8V5V3V6V7V1V2V3V4V5V8V6V7深度优先:深度优先:广度优先:广度优先:生成树二、算法二、算法图的遍历算法访问了图中的每个顶点一次图的遍历算法访问了图中的每个顶点一次且仅一次。且仅一次。访问某个顶点的邻接点时,要经过与这两访问某个顶点的邻接点时,要经过与这两个顶点相关联的边。个顶点相关联的边。因此,图的遍历算法可以产生一颗生成树:因此,图的遍历算法可以产生一颗生成树:所有的顶点和经过的边。所有的顶点和经过的边。生成树算法void DFSTree(Graph G,int v,CSNode T) =true; first=true; for(w=FirstAdjVex(G,v);w=0; w=NextAdjVex(G,v,w) )p= new CSNode(v);if(first) =p;first=false

      2、; else =p;q=p;); SG1SG2SG3Vw1w3w2算法算法以孩子以孩子兄弟链表作兄弟链表作为生成森林为生成森林的存储结构的存储结构生成森林一、定义一、定义 非连通图非连通图G的每个连通分量的生成树,的每个连通分量的生成树,构成了图构成了图G的生成森林的生成森林生成森林abchdekfg812345670812345670abchdekfg非连通图非连通图G:G的深度优先搜索生的深度优先搜索生成森林:成森林:achdfekbg生成森林算法算法算法以孩子以孩子兄弟链表作兄弟链表作为生成森林为生成森林的存储结构的存储结构void DFSForest(Graph G, CSNode T)T=null;for(v=0;v=G.vexnum;+v)=false;for(v=0;v=G.vexnum;+v)p=new CSNode(v)if(!T) T=p;else =p;q=p;DFSTree(G,v,p);最小生成树 假设要在假设要在 n n 个城市之间建立通讯联络个城市之间建立通讯联络网,则连通网,则连通 n n 个城市只需要修建个城市只需要修建 n-1n-1条线条线路,路,如

      3、何在最节省如何在最节省经费经费的前提下建立这个通的前提下建立这个通讯网讯网?问题:问题:最小生成树连通网:连通网:n个城市和城市间个城市和城市间可能的通信线路可能的通信线路网的顶点:网的顶点:表示城市表示城市网的边:网的边:表示两个城市之间表示两个城市之间的线路的线路网的边上的权值:网的边上的权值:通信代价通信代价2452710614v4v5v1v3v2v6v7138最小生成树22614v4v5v1v3v2v6v712452710614v4v5v1v3v2v6v7138最小生成树 构造网的一棵最小生成树,即:在e条带权的边中选取n-1条边(不构成回路),使“权值之和权值之和”为最小。该问题等价于:特点:1.最小生成树中边的条数为|V|-1。2.最小生成树无圈。3.最小生成树是包含所有顶点的的最小的树。最小生成树算法三:克鲁斯卡尔算法算法三:克鲁斯卡尔算法KruskalKruskal算法二:普里姆算法算法二:普里姆算法PrimPrim算法一:破圈法算法一:破圈法破圈法一、一、基本思想基本思想1、将所有的边按权重从大到小排列。2、对每条边e尝试下面的操作,直到G中的边数=n-1: 如果删除

      4、e, 图G仍然是连通图,则从G中删除e 否则,保留e。破圈法v4v5v1v325v2v6v711064724138破圈法abcdegf195141827168213127课堂练习:Prim算法算法思想:使最小生成树连续的一步步成长。在每一步,都要把一个节点当作根并往上加边,这样相关联的顶点就加到增长中的树上。Prim算法 在生成树的构造过程中,图中n个顶点分属两个集合:已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U,则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。UV-UPrim算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7122416Prim算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7122416vknowndvpvv1v2v3v4v5v6v7FFFFFFF00000000Tv1241Tv4v1v1v12v47v48v44v4Tv2Tv3Tv76v7Tv6Tv55v31v7算法的核心:选择向集合U中加入顶点时,要选择到U具有最短边的顶点。1、对任何一个顶点v,如果它有多个邻接U的边

      5、,则需要找出最短的边作为邻接到U的边2、从所有的V U顶点中,找出具有最短边的顶点,将它加入UPrim算法abcdegf195141827168213127abegf14d8c351621Prim算法Kruskal算法具体做法: 先构造一个只含n个顶点的子图SG,然后从权值最小的边开始,若它的添加不使SG中产生回路,则在SG上加上这条边,如此重复,直至加上n-1条边为止。考虑问题的出发点: 为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小。abcdegf3abcegfd 21581416Kruskal算法Kruskal算法v4v5v1v325v2v6v711064724138v4v5v1v3v2v6v7112246算法描述算法描述: :构造非连通图构造非连通图 ST=(V, );ST=(V, ); k=i=0; / k k=i=0; / k 选中的边数选中的边数 while (kn-1) while (kn-1) +i; +i; 检查边集检查边集E E中第中第i i条权值最小的边条权值最小的边(u,v);(u,v); if if 若若(u,v)(u,v)加入加入STST后不使后不使STST中产生回路中产生回路, 则输出边则输出边(u,v);(u,v); 且且k+;k+; Kruskal算法两种算法的比较普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名称算法名称适应范围适应范围课堂练习求出图中最小生成树abed8c9244756小结和作业1.普里姆算法普里姆算法2.克鲁斯卡尔算法克鲁斯卡尔算法 3. 两种算法的比较两种算法的比较 2. 最小生成树算法最小生成树算法1.图的生成树和生成森林图的生成树和生成森林作业:作业:P275,9.15,

      《数据结构(牛小飞)5最小生成树》由会员cn****1分享,可在线阅读,更多相关《数据结构(牛小飞)5最小生成树》请在金锄头文库上搜索。

      点击阅读更多内容
      1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
      2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
      3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
      4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
      5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
      6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
    新上传的文档
    【6篇文】2025年“四个带头”方面生活会个人检视检查材料(含反面案例、典型案例剖析)+存在问题示例50条 2025年“四个带头”发言材料6篇 2025年专题生活会“四个带头”领导干部对照检查材料(含反面典型案例)+检视问题台账20条+意见建议6份材料 2025年“四个带头”方面生活会个人检视检查材料(含反面案例)与批评与自我批评材料(14个方面28组)6篇文 2025年“四个带头”存在的问题原因及今后努力方向个人检视检查材料(含反面案例)6篇例文 2025年“四个带头”存在的问题、原因分析、改进措施、个人检视解析材料6篇文 2025年生活会个人检视材料【违纪行为典型案例剖析】、主持词、“四个带头方面”对照个人检查材料6篇例文 2025年带头严守政治纪律和政治规矩方面等“四个带头”方面对照个人检视发言材料6篇文 【数学】整式的乘法基础过关测试卷++2024-2025学年北师大版数学七年级下册 【数学】第2课时幂的乘方教学设计2024-2025学年北师大版数学七年级下册 【语文】第20课《外国诗二首》课件+2024—2025学年统编版语文七年级下册 【地理】亚洲及欧洲第二课时气候教学设计-2024-2025学年七年级地理下学期(湘教版2024) 【数学】用坐标表示平移 教学设计++2024-2025学年人教版数学七年级下册 【语文】第5课《黄河颂》课件+2024-2025学年统编版(2024)语文七年级下册 【地理】澳大利亚 课时作业-2024-2025学年+七年级地理湘教版(2024)下册
    最新标签
    公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇 农村发展调研报告_1范文 2022年电脑说明文作文合集六篇 2022年防溺水初中生演讲稿 2021最新36岁儿童学习与发展指南心得体会 2022年新生迎新晚会策划书模板 20 xx年教育系统计划生育工作总结 英语定语讲解ppt课件 2021年4s店客服工作计划范文 2022年小学优秀作文700字四篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.