最小生成树的算法及其应用开题报告

1. 研究目的与意义

树在图论里是一个重要的概念，它是所有图中极为简单又极为重要的一类图，而最小生成树的理论和计算，在很多工程或技术领域中得到应用。

首先，现实中一些实际应用问题可通过利用连通图、生成树的模型来建立求解，找出最优的方法，而在任意一个连通图中存在许多条生成树，如何从这些生成树中找出一条权最小的生成树对解决现实生活中实际应用问题具有重大意义。

然后，我们生活在一个网络社会中。

2. 研究内容和预期目标

研究内容：最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树,也就是在所有生成树中总的代价最小的生成树。

kruskal算法和prim算法是求最小生成树的常用算法。

本文主要研究了kruskal算法的实现过程及其应用。

3. 国内外研究现状

目前，求最小生成树的算法已经相当成熟，常用的经典算法有：kruscal算法，prim算法，sollin算法，dijkstra算法等。

最小生成树在今后的实际生活中会得到越来越广泛的应用。

例如，城市中高速公路的铺设，通讯网络的构建，露天矿排水系统的设计等，要求总的线路长度最短或材料最省，成本最低等，这类问题归结起来都是求最小生成树。

4. 计划与进度安排

2022年11月10日前--完成选题工作2022年11月30日前--完成开题工作2022年1月20日前--收集资料、开展论文2022年3月18日前--完成初稿和中期检查工作2022年4月30日前--完成论文修改、定稿、外文文献翻译工作2022年5月25日前--完成答辩环节工作

5. 参考文献

[1]胡运权,运筹学教程.清华大学出版社[2]破圈法构造最小生成树算法探讨[J]. 龙亚.毕节学院学报. 2007(04)[3]基于Kruskal算法的最短路径算法研究[J]. 王英,刘天时.重庆文理学院学报(自然科学版). 2009(06)[4]李春葆,数据结构与算法教程第二版.等,清华大学出版社[5]殷剑宏,图论及其算法.中国科学技术大学出版社 [6]谭浩强,C语言程序设计(第三版).清华大学出版社[7]最短路径算法在城市导航中的应用[J]. 梅青平.科技信息. 2010(32)[8]并行最短路径搜索算法的设计与实现[J]. 卢照,师军.计算机工程与应用. 2010(03)[9]最小生成树算法及其在经济应用中的意义[J]. 赵白云,欧建华.河南商业高等专科学校学报. 1999(02)[10]一种基于Dijkstra的海量空间数据最短路径算法[J]. 张福浩,刘纪平.辽宁工程技术大学学报(自然科学版). 2009(04)[11]求最小生成树的矩阵算法[J]. 毛华,史田敏,高瑞.郑州大学学报(理学版). 2013(04)[12]求解度约束最小生成树的一种改进算法[J]. 贾青慧.计算机应用与软件. 2012(05)[13]最小生成树的应用及拓展探讨[J]. 胡红.洛阳师范学院学报. 2012(02)[14]图的最小生成树的构造方法探究[J]. 刘建科.电脑知识与技术. 2017(12)[15]An axiomatic approach in minimum cost spanning tree problems with groups Gustavo Bergantintilde;os; Mara Gmez-Ra