信息学-最小生成树

信息学-最小生成树信息学-最小生成树图论之最小生成树最小生成树一、生成树的概念若图是连通的无向图或强连通的有向图，则从图中任意一个顶点出发调用一次bfs或dfs后，便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs，亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图，称为原图的生成树。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。具有n个顶点的带权连通图，其对应的生成...

信息学-最小生成树图论之最小生成树最小生成树一、生成树的概念若图是连通的无向图或强连通的有向图，则从图中任意一个顶点出发调用一次bfs或dfs后，便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs，亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图，称为原图的生成树。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。具有n个顶点的带权连通图，其对应的生成树有n-1条边。二、最小生成树如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。对于带权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树，称为图的最小生成树。求图的最小生成树具有很高的实际应用价值。【例1】城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100）； e（边数）； 1

                    本文档为【信息学-最小生成树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

你可能还喜欢

最新资料

资料动态

专题动态

is_954223

暂无简介~

格式：doc

大小：5KB

软件：Word

页数：0

分类：初中语文

上传时间：2017-06-02

浏览量：14

热点搜索

部队基层政治工作都包括哪些方面【精选资料】讲解员大赛知识问答参考题目主体结构实体检测广东东莞莞城话的_起_ 会计专业社会实践报告运动康复治疗中心简介组织部内部考核表我市暂未发现福建“假牛肉干”(图) 【doc】重金属污染黑土中固氮菌及反硝化菌作用强度的测定小学生爱国主义小故事 2023关于财务部工作计划合集6篇配制0.2M磷酸缓冲液的方法钢结构课程设计报告之三角形钢屋架设计物理人教版八年级上册5.4 《眼睛和眼镜》教学反思部队基层政治工作都包括哪些方面【精选资料】讲解员大赛知识问答参考题目主体结构实体检测广东东莞莞城话的_起_ 会计专业社会实践报告运动康复治疗中心简介组织部内部考核表我市暂未发现福建“假牛肉干”(图) 【doc】重金属污染黑土中固氮菌及反硝化菌作用强度的测定小学生爱国主义小故事 2023关于财务部工作计划合集6篇配制0.2M磷酸缓冲液的方法钢结构课程设计报告之三角形钢屋架设计物理人教版八年级上册5.4 《眼睛和眼镜》教学反思