为生存而奔跑

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

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319333
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

我认为判断prim算法唯一性有两个方面:

1.假设目前已经生成的集合为P,现在需要把集合P外的距P最近的点a加到集合P中。在这个过程中,如果a与集合P中的b、c都构成了最短距离,则此时把a加入到P中有两种方式即:与b相连和与c相连,这就完完全全成为了两棵不同的最小生成树。

2.假设目前已经生成的集合为P,现在需要把集合P外的距P最近的点a加到集合P中。在这个过程中,如果a、b分别与集合P中的x、y都构成了最短距离,则此时同样有两种方式即:加入a和加入b。但是,这两种方式不一定形成不同的树。

为此,我们需要加入另外的条件,当a、b分别与P中的x、y构成最短距离,不妨先把a加入其中形成P',如果此时b到P'中y的距离和b到P中y的距离相等且还是最短距离,则还是同一棵树。否则,构成了两棵不同的最小生成树。

posted on 2009-07-20 16:52 baby-fly 阅读(781) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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