摘要最小生成树是近代网络（如水利流通管道网络、电力系统网络、交通枢纽网络、电信电话网络等）的一个非常重要的图论问题，算法在解决系统设计和搭建中起着非常重要的作用。求解最小生成树的问题就是求网络路的具备最小权重的生成树，而本文中我们将分别介绍贪心算法和Boruvka算法。贪心算法在求解对最小生成树问题的时候，遵循做出当前看似最理想的选择。换一种说法，即不以追求全局最优结果以考虑，它追求做出的是局部最优解。有两个算法是以贪心算法为基础的，一个是Kruskal（克鲁斯卡尔）算法，一个是Prim（普利姆算法），这两种算法的基础核心思想都是贪心算法，了解这两个算法也可以对算法优化有更深入看法。Boruvka算法也是由贪心算法为根基，但是在运算上其主要的思想是通过先完整收集合理的路径然后舍弃较长的路径，以达到算法最后最小权重的目的。78416

通过比较贪心算法和Boruvka算法这两个算法在同一个图求解过程中算法的复杂性和权重对比来讨论两者的优劣。归纳为二个分论题来阐述：

一、贪心算法及Boruvka算法的基本内容及算法论证方法；

二、从算法内容简便和结果精确角度将Boruvka算法与贪心算法进行比较分析。

毕业论文关键词：生成树算法；贪心算法；Boruvka算法

Abstract Minimum spanning tree is a very important theme in graph theory in the field of modern network, such as the pipeline network of water circulation, power system network, traffic network, Telegraph and telephone networks, etc。 What’s more, it plays a very important role in the theme of graph theory in solving the system design and architectures。 Solving the minimum spanning tree problem is equal to finding minimum weight spanning tree , and in this paper we will introduce the greedy algorithm and Boruvka algorithm。 Greedy algorithm, refers to the problem in solving the problem, always makes the best choice in the current view。 That is to say, without considering as a whole, it makes the local optimal solution in some sense There are also two algorithms on the base of greedy algorithm, one is the Kruskal algorithm, and the other is prim algorithm。 The understructure of the two algorithms are greedy algorithm, understanding this two algorithms can show more in-depth view of algorithm optimization。 Boruvka algorithm is as greedy algorithm as the foundation, but its main idea is through the first complete rational collect path then give up a long path to achieve the algorithm for the minimum weight in operation。

We use the greedy and Boruvka algorithm in the same process of solving graph algorithm to learn about their complexity and weight, contrast to discuss both the advantages and disadvantages。 Summarized into two sub topics to explain:

Firstly, demonstrates the basic content and method of greedy algorithm and Boruvka algorithm ;Secondly, from comparing the simplicity and accuracy of the Bruvka algorithm and greedy algorithm。

Keywords: Minimum spanning tree；Greedy Algorithm；Boruvka algorithm

目  录

第一章 绪论 -1

1。1 研究背景1

1。2 最小生成树研究的进展及成果2

1。3 本文的主要内容3

第二章 生成树的Boruvka算法相对经典算法的优势讨论-5

2。1 基本概念5

2。1。1 最小生成树算法5

2。1。2 贪心算法基础介绍7

2。1。3。与贪心算法相关的两个算法9

2。1。4 Boruvka算法的基础介绍11

2。2 两个生成树算法对比优势讨论-13

2。3 小结-14

结论15

致谢16

参考文献-17

第一章 绪论

1。1 研究背景

为了满足科技发展对大数据及信息化处理的需求,伴随计算机信息技术飞速的发展、编程语言的应用技术不断提高,线性规划、贪婪策略等一系列运筹学学科的算法模型接二连三地被在计算机算法学中广泛运用,因而产生了各种解决各种现实问题的有效算法。论文网