毕业论文

当前位置: 毕业论文 > 数学论文 >

最小生成树算法及其应用研究

时间:2017-12-04 19:05来源:毕业论文
论文根据最小生成树算法的特点,研究了它的三种求解方法:普里姆(Prim)算法、克鲁斯卡尔(Kruskal)算法、简易算法.并且通过对这三种算法的分析研究
摘要:在科学研究和生活实践中,许多问题都可以转化为求解连通图的最小生成树算法的应用问题,因此最小生成树的算法及其应用研究在科学与现实生活中有着广泛的应用.本毕业论文根据最小生成树算法的特点,研究了它的三种求解方法:普里姆(Prim)算法、克鲁斯卡尔(Kruskal)算法、简易算法.并且通过对这三种算法的分析研究,设计了它们简单的算法步骤.本文结合实际生活中的一些现实问题,利用最小生成树的生成算法,找出最简捷快速的方法来达到目的,解决问题,从而提高其经济效益.16103
关键词:连通图;最小生成树;普里姆算法;克鲁斯卡尔算法;简易算法
The research of Minimum Spanning Tree Algorithm and its Application
Abstract: In the scientific research and practice, many problems can be transformed into solving the application problems of minimum spanning tree algorithm of connected graph, so the minimum spanning tree algorithm and its application has been widely used in science and real life. In this paper, based on the characteristics of the minimum spanning tree algorithm, studied its three solving methods: Prim algorithm, Kruskal algorithm, Simple algorithm. Through the analysis and study of the three algorithms, this paper designs their simple algorithm steps. Combined with some practical problems in actual life, this paper use the minimum spanning tree generation algorithm to find the most simple and quick way to achieve the goals, solve the problems and improve their economic efficiency.
Key words: Connected graph; Minimum spanning tree; Prim algorithm; Kruskal algorithm; Simple algorithm
目    录
摘  要    1
引言    2
1.预备知识    3
1.1图的连通性问题    3

源自六-维+论\文"网*加7位QQ3249.114 www.lwfree.cn


1.2图的生成树    3
2.普里姆(Prim)算法    4
2.1理论依据    5
2.2算法思想步骤    5
2.3算法步骤    6
2.4实例应用    6
3.克鲁斯卡尔(Kruskal)算法    10
3.1理论依据    10
3.2算法思想步骤    10
3.3算法步骤    11
3.4实例应用    11
4.简易算法    14
4.1理论依据    14
4.2算法思想步骤    14
4.3算法步骤    14
4.4实例应用    14
5.结束语    16
参考文献    18
致 谢    19
最小生成树算法及其应用研究 引言
在经济发展越来越快的今天,建设和发展城镇,已成为中国经济发展战略的重要组成部分,发达的交通、便利的网络、经济的电气煤气输送系统,对于中国城市群迅速发展将起到积极、巨大的推动作用,20世纪的今天,随着计算机的发展和普及,以及其计算的迅速准确性,人们开始研究应用计算机来解决现实中的这些问题,因为不同的方法耗时和经费均不同,因此在求解这些问题时找到一种既简便又高效的方法成为人们越来越追求的目标.
而现实生活中的这些实际问题都可以通过利用连通图、生成树的模型来建立求解,找出最优的解决方法,而在任意的一个连通图中都存在着许多生成树,如何在这些生成树中找出一条权值最小的生成树对于解决生活实际应用问题具有重大意义,文献[1]主要对图和树的知识进行研究,并对最小生成树也进行了研究,以及简单介绍了最小生成树的生成方法.经过许多数学家长期的探索研究,目前求解最小生成树的算法主要有三种,普里姆算法(Prim算法)、克鲁斯卡尔算法(Kruskal算法)和简易算法,文献[2]-[9]对于这三种算法进行了深入的研究,使这三种算法更容易理解,文献[10]-[11]主要通过生活中的实例对这三种算法进行了解释,这三种算法在现实生活中得到了很广泛的应用,其在计算机上的实现也关系着问题解决效率的提高,因此这三种算法的计算机语言程序也应运而生. 最小生成树算法及其应用研究:http://www.lwfree.cn/shuxue/20171204/17291.html
------分隔线----------------------------
推荐内容