矩阵形网络图最小生成树算法的优化  

The Optimization of Constructing Minimum Spanning Tree for Grid Graph

作　　者：刘恒殊[1] 黄廉卿[1] 

机构地区：[1]中国科学院长春光学精密机械与物理研究所虚拟技术部,长春130022

出　　处：《计算机工程与应用》2002年第3期54-55,共2页Computer Engineering and Applications

基　　金：中国科学院青年创新基金(编号:ZJ00O01D)

摘　　要：最小连接问题在网络优化中有广泛的应用,找到快速有效的算法来构造最小生成树是解决问题的关键。该文提出了一种构造算法,在存储结构和排序方法两方面进行了改进。从理论上分析了算法的计算复杂度,并实际测试了算法运行时间。结果表明该算法较现有算法有了很大提高。The smallest connection problem is widely used in network optimization.The key of solution is to find a minimum spanning tree with rapid and effective algorithm.This paper presents a new algorithm to construct minimum spanning tree.The store structure and the sort technique are optimized in this algorithm.Theoretical analysis and experiment results show the algorithm has less computational complexity.

关 键 词：数据结构 二叉排序树 矩阵形网络图 优化 最小生成树算法 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]