一种求解最小生成树问题的算法

摘要

This paper presents an algorithm for solving Minimum Spanning Tree(MST) problem based on the node combination and reverse direction tracing method. According to the adjacent matrix, the source node and the adjacent nodes are combined into new source node repeatedly and all the nodes in the network are combined into one single node. By introducing the front point label array, it gets the MST. The correctness and complexity of the algorithm are analyzed. It applies the algorithm to the highway system engineering construction plan, the results prove the validity of the algorithm.%基于节点合并和反向追踪的思想,提出一种求解最小生成树问题的算法.该算法依据网络邻接矩阵,将与源节点相邻的节点逐步合并为新的源节点,使网络中的所有节点合并为一个点,借助引入的前点标号数组得到网络的最小生成树,对算法正确性与算法复杂度进行分析.将该算法应用于某高速公路网工程建设方案,结果证明了算法的有效性.