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

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

探讨了最小生成树的实现问题,分析了基于各种优先队列机制下算法的实现性能,讨论了次小生成树的性质,提出了时间复杂性为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.