首页 > 代码库 > 次优最小生成树<提纲>

次优最小生成树<提纲>

时间有限,先占坑,写下主体思路,以后有空填

prim算法中,选择横跨切割的边时,比如选择了(u,v),那么它一定在所有已选节点到v的路径上,此时更新所有已选节点到v的路径上的最大权重边。prim算法结束后,便得到最小生成树中,任意两节点间的简单路径中最大权重边。

枚举图G中所有不属于最小生成树T的边,将一条边添加到T中,便得到一个环,删除环中除了新加入的边以外最大权重的边,便得到一棵总代价大于等于T的生成树。选则最小的那个,便是次优最小生成树。

类似的方法还可以判断最小生成树是否唯一,简言之,对于不属于T的一条边(u,v),若T中u和v两节点间路径上最大权重边与(u,v)权重相等,则T加入(u,v)并删除这个最大权重边后,T总代价不变,也就是说,最小生成树不唯一。

<来自算法导论第三版23章思考题>

次优最小生成树<提纲>