计算机工程2011，Vol.37Issue(23)：241-243,247,4.
一种求解最小生成树问题的算法
Algorithm for Solving Minimum Spanning Tree Problem
摘要
Abstract
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.关键词
最小生成树/节点合并/反向追踪/前点标号数组/邻接矩阵Key words
Minimum Spanning Tree(MST)/ node combination/ reverse direction tracing/ front point label array/ adjacent matrix分类
数理科学引用本文复制引用
孙小军,刘三阳,王志强..一种求解最小生成树问题的算法[J].计算机工程,2011,37(23):241-243,247,4.基金项目
陕西省教育厅专项科研计划基金资助项目(11JK0509) （11JK0509）
宝鸡文理学院基金资助重点项目(ZK0931) （ZK0931）
