为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319329
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

次小生成树的两种算法:
算法1、step 1.  先用prim求出最小生成树T.
         在prim的同时,用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
         路中权值最大的那条边的权值. (注意这里).
         这是很容易做到的,因为prim是每次增加一个结点s, 而设已经标号了的结点
         集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
         step 1 用时 O(V^2).
     step 2.  枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。
算法2、先用prim求出最小生成树T。
           枚举T中的每一条边,把它删除,求剩下的图的最小生成树。选所有枚举得到的生成树中的最小的那一个。

posted on 2009-07-14 15:55 baby-fly 阅读(1172) 评论(2)  编辑 收藏 引用 所属分类: Algorithm

Feedback

# re: 次小生成树算法[未登录] 2011-07-07 08:29 c
请问哪种算法效率高?  回复  更多评论
  

# re: 次小生成树算法 2012-02-08 11:13 EUYUIL
有点不太明白“W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.”,即将加入的边似乎不一定是最长的。  回复  更多评论
  


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