独立博客: 哲学与程序

哲学与程序

最小树形图

何谓最小树形图,最小树形图,在一个有向图中,定义某个节点为根节点,由该根节点扩展出来的一颗有向的生成树,并且使这棵树的权值最小。练习题POJ3164
解决该问题的算法有两位中国人提出,有位同学将该论文总结一下:
最小树形图算法(Zhu-Liu Algorithm):

1.  设最小树形图的总权值为cost,置cost为0。

2.  除源点外,为其他所有节点Vi找一条权值最小的入边,加入集合T。T就是最短边的集合。加边的方法:遍历所有点到Vi的边中权值最小的加入集合T,记pre[Vi]为该边的起点,mincost[Vi]为该边的权值。

3.  检查集合T中的边是否存在有向环,有则转到步骤4,无则转到步骤5。这里需要利用pre数组,枚举检查过的点作为搜索的起点,类似dfs的操作判断有向环。

4.  将有向环缩成一个点。设环中有点{Vk1,Vk2,…,Vki}共i个点,用Vk代替缩成的点。在压缩后的图中,更新所有不在环中的点V到Vk的距离:

map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=i;

map[Vk][V] = min {map[Vkj][V]}           1<=j<=I

5.  cost加上T中有向边的权值总和就是最小树形图的权值总和。

posted on 2011-05-26 13:22 哲学与程序 阅读(727) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序