首页 > 代码库 > 生成树问题(1)
生成树问题(1)
最小瓶颈生成树:(给出加权无向图,求一棵生成树,是的最大边权尽量小)
可以从一个空树开始,按照权值从小到大,依次加入各条边,则图第一次连通的时候,改图的最小生成树就是原图的最小瓶颈生成树。
这一过程就是Kruskal,原图的最小生成树就是一棵最小瓶颈生成树。
最小瓶颈路:(u,v,求一条路径从 u 到 v ,是的路径上的最长边短)
1、可以用 Dijkstra 松弛条件的变形;
2、二分答案,看这个结果是不是可以使得 u 到达 v ,怎么看 u 是否能够到达 v ,就是 BFS;
3、先求出这个图的最小生成树。则 u 和 v 在书上的唯一路径就是要找的路径,这个路径上的最长边,就是最小瓶颈;
每对结点间的最小瓶颈路:
这个问题在上一篇文章中提到,再复习一下;http://www.cnblogs.com/TreeDream/p/6135786.html
有了前面的经验,不难想到先求出最小生成树。
接下来,用DFS吧最小生成树变成有根树,同时计算 f(u,v);
当新访问一个结点 u 的时候,考虑所有已经访问过的老结点 x ,更新 f(x,u) = max( f(x,v) , w(u,v) ) (v 是 u 的父亲结点);
生成树问题(1)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。