主要介绍了详解次小生成树以及相关的C++求解方法,文中的练习示例采用了kruskal算法通过C++进行求解,需要的朋友可以参考下

次小生成树的定义 设 G=(V,E,w)是连通的无向图，T 是图G 的一个最小生成树。如果有另一棵树T1，满 足不存在树T’,ω（T’）<ω（T1） ，则称T1是图G的次小生成树。 求解次小生成树的算法 约定：由T 进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集,记为N(T)。 定理 3：设T是图G的最小生成树，如果T1满足ω(T1)=min{ω(T’)| T’∈N(T)},则T1是G 的次小生成树。 证明：如果 T1 不是G 的次小生成树，那么必定存在另一个生成树T’,T’