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

探讨了最小生成树的实现问题,分析了基于各种优先队列机制下算法的实现性能,讨论了次小生成树的性质,提出了时间复杂性为O(n2)的次小生成树算法。

最小生成树是否唯一

最小生成树是图论的经典问题，求最小生成树以及求最小生成树的权值和得到了足够关注，而很少人去研究最小生成树是否唯一。对于给定的图而言，因为最小生成树的权值和是确定的，所以最小生成树不唯一当且仅当最小生成树的形状不唯一。本文提出判断最小生成树是否唯一的三种方法并且对它们给予分析和评价。