基于最小树权矩阵法的改进算法  

Improved algorithm based on weight matrix method for minimum-spanning-tree problem

作　　者：孙小军[1] 刘三阳[1] 焦建民[2] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071 [2]宝鸡文理学院数学系,陕西宝鸡721007

出　　处：《计算机工程与设计》2005年第12期3274-3275,共2页Computer Engineering and Design

基　　金：陕西省自然科学研究基金项目(2003A09)

摘　　要：针对最小树权矩阵法在大型网络应用中的不足,从提高算法效率方面对其进行了改进,并给出了新的算法。新算法减少了运算量,达到了快速寻找最小树的目的。通过对新算法和权矩阵法的比较,结果表明新算法具有较低的复杂度,是一种更为有效的算法。To correct the shortcomings of weight matrix method for the minimum-spanning-tree problem in applications of the large net-work,an new algorithm was presented,which was obtained by improving the efficiency of weight matrix method.The algorithm could reduce superfluous calculation and find the MST of the network more quickly.By comparing the two algorithms,the results show that the new algorithm has lower complexity and higher efficiency in finding the MST of the network.

关 键 词：网络 最小树 权矩阵 算法 复杂度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]