最小生成树与次小生成树上的算法分析与设计  

The Design and Analysis of Algorithms on the Minimum Spanning Tree and Second-best Minmum Spanning Tree

作　　者：周玉林[1] 

机构地区：[1]上饶师范学院,江西上饶334001

出　　处：《上饶师范学院学报》2005年第3期79-82,共4页Journal of Shangrao Normal University

摘　　要：探讨了最小生成树的实现问题,分析了基于各种优先队列机制下算法的实现性能,讨论了次小生成树的性质,提出了时间复杂性为O(n2)的次小生成树算法。<Abstrcat>we investigate the problem of realization on the minimum spanning tree, we analyse the performances of different priority queues on the alogirhms of the problem of minum spanning tree, discusses the performance of the second-best spanning tree, and we gives a time o(n^2) algorithm on the second-best spanning tree.

关 键 词：优先队列 贪心算法 最小生成树 Fibonacci堆 次小生成树 

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