最小生成树有两种算法:Prim和Kruskal,这里说一下Kruskal算法。
其具体算法描述为(我们假设给定的图是连通的):
1.初始化总花费allcost=0
2.将所有边按边长len从小到大的顺序排序
3.从头到尾依次遍历个边edge[i], 如果该边关联的两个定点不属于同一个集合,则将这两个集合合并,并更新allcost。
Kruskal算法牵涉到集合操作,包括集合的建立和集合的合并,这里用并查集解决,下面简单介绍以下并查集。
并查集用森林来表示,他有以下操作:
初始化:把每个节点所在结合初始化为自身。
查找:查找元素所在的集合,即根节点
合并:将两个在不同集合的元素合并为一个集合,为了保持数的深度的平衡性,在合并之前,应判断两个集合树的深度,如果深度不同,应将深度小的合并到深度大的上面。
关于维持集合树深度的问题,还有另一种做法,就是合并集合的时候并不考虑树的深度,而是在查询的时候改变树的深度。因为没有写过,这里不多说了。
下面是poj1258的代码,最直接的最小生成树。
posted on 2012-08-04 14:24 小鼠标 阅读(1605) 评论(0)  编辑 收藏 引用 所属分类: 图论

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


<2012年8月>
2930311234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜