首页 > 代码库 > 次优最小生成树<提纲>
次优最小生成树<提纲>
时间有限,先占坑,写下主体思路,以后有空填
prim算法中,选择横跨切割的边时,比如选择了(u,v),那么它一定在所有已选节点到v的路径上,此时更新所有已选节点到v的路径上的最大权重边。prim算法结束后,便得到最小生成树中,任意两节点间的简单路径中最大权重边。
枚举图G中所有不属于最小生成树T的边,将一条边添加到T中,便得到一个环,删除环中除了新加入的边以外最大权重的边,便得到一棵总代价大于等于T的生成树。选则最小的那个,便是次优最小生成树。
类似的方法还可以判断最小生成树是否唯一,简言之,对于不属于T的一条边(u,v),若T中u和v两节点间路径上最大权重边与(u,v)权重相等,则T加入(u,v)并删除这个最大权重边后,T总代价不变,也就是说,最小生成树不唯一。
<来自算法导论第三版23章思考题>
次优最小生成树<提纲>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。