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

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.预备知识    3
1.1图的连通性问题    3

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

------分隔线----------------------------