首页 > 代码库 > 生成树问题(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)