最新消息:点击查看大S的省钱秘笈

最小生成树kruskal算法并查集版 C语言实现

编程相关 Slyar 605浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

今天数据结构课讲了最小生成树的Kruskal算法和Prim算法,不过都只是概念,可能是怕他们听不懂吧,反正算法实现一概不讲...囧

下午抱着《算法导论》跑去图书馆看Kruskal算法,发现《算法导论》真的是牛XXXX的书啊,看完之后豁然开朗,而且惊讶地发现Kruskal算法居然用到了前两天研究的并查集,爽歪歪了...

Kruskal比较适用于稀疏图,是一种贪心算法:为使生成树上边的权值和最小,则应使生成树中每一条边的权值尽可能地小。

具体做法:找出森林中连接任意两棵树的所有边中,具有最小权值的边,如果将它加入生成树中不产生回路,则它就是生成树中的一条边。这里的关键就是如何判断"将它加入生成树中不产生回路"。

《算法导论》提供的一种方法是采用一种"不相交集合数据结构",也就是并查集了。具体的实现看代码好了,反正核心内容就是如果某两个节点属于同一棵树(Find_Set),那么将它们合并(Union)后一定会形成回路

编写程序:对于如下一个带权无向图,给出所有边以及权值,用kruskal算法求最小生成树。

kruskal

输入数据:

11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11

输出:

A - D : 5
C - E : 5
D - F : 6
A - B : 7
B - E : 7
E - G : 9
Total:39

代码如下,其实代码可以优化的地方很多,例如当生成树的边数已经等于n-1时即可停止循环...因为不是ACM题,故优化省略不写,只当做算法学习...

转载请注明:Slyar Home » 最小生成树kruskal算法并查集版 C语言实现

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (27)

  1. 还有怎样才能知道我所合并的两个集合各自的元素个数?
    2年前 (2015-05-17)回复
  2. 菜鸟一枚,求问为何 1.if (rank == rank ) { rank ++; } 2.if (x != y || (!x && !y))中的 (!x && !y)的含义
    2年前 (2015-05-17)回复
  3. 该程序有BUG,可以尝试只输入3个顶点的边,AB,AD,BD,此时AD的边就会被忽略掉,所以本程序只适合顶点连续(ABC)的输入数据,对于顶点排序不连续的结果则出错(如ABD)。归根到底是MakeSet函数不能针对边来使用
    s2年前 (2014-09-26)回复
    • 嗯 说得对,不相连的边需要单独考虑
      Slyar2年前 (2014-09-27)回复
  4. 清晰易懂。赞一个。
    沧海月明4年前 (2013-02-08)回复
  5. lz很强大。。。评论看得我很无语。。
    匿名6年前 (2011-06-14)回复
  6. @Slyar 不过union 的参数怎么好像是一个边的xy,没有另一个边的呢?
    mingbo6年前 (2011-05-19)回复
  7. @Slyar 啊哈,博主威武...我当时自己在实现的时候用点在union。 借用了您的实现思路...啊哈~~~也给实现了。
    mingbo6年前 (2011-05-19)回复
  8. @mingbo =_=一直都是对边进行操作
    Slyar6年前 (2011-05-18)回复
  9. 代码思路没有问题,实现上有问题。 比如一条边的2个点,一个用来union了,用另外一个点查询集合怎么办?
    mingbo6年前 (2011-05-18)回复
  10. 请问下您这个程序 如何判断不能生产最小生成树的情况 如果不能生产 输出impossible 怎么改? 谢谢
    gf6年前 (2010-12-04)回复
  11. 非常无比之透彻清晰………………
    一棵小草6年前 (2010-08-31)回复
  12. @gongzhi 我无语,不解释,你自己随便想好了...
    Slyar7年前 (2010-05-27)回复
  13. 版主,那个Make_Set(i);初始话应该错了,因为集合是顶点的集合,你这样初始化把它看成了边的集合,我就是看成边的集合一直WA,后面改了才对的
    gongzhi7年前 (2010-05-27)回复
  14. @chhaya 恩,很好,至少原理没错
    Slyar7年前 (2009-08-31)回复
  15. @Slyar 原来是为了省事啊,那我无语了。
    chhaya7年前 (2009-08-31)回复
  16. @chhaya 囧……father数组是保存父节点的啊,一开始大家的父节点都是自己,跟边有什么关系呢? 哦,你是说我调用Make_Set()的那个循环么?我那其实是为了省事,因为边数肯定是大于等于顶点个数的...
    Slyar7年前 (2009-08-31)回复
  17. @Slyar ok,你的father那么初始化不对的吧,那个应该是针对每个顶点的,而你是对每条边.... 你自己想想
    chhaya7年前 (2009-08-31)回复
  18. @chhaya 谢谢您,能不能具体点,错了总得有点理由吧...
    Slyar7年前 (2009-08-30)回复
  19. 你那个错了啦!
    chhaya7年前 (2009-08-30)回复
  20. @Felix021, 输出肯定一样...囧
    Slyar8年前 (2009-06-02)回复
  21. @Slyar Orz 按秩合并是可以减少高度,但是随机合并实现起来比较容易,效果应该也不差。 我昨天测了下,我的程序输出结果和你的一样。
    Felix0218年前 (2009-06-02)回复
  22. @Felix021, 空行、注释、变量定义分行...无视长度... 按秩合并不是可以减少树的高度,然后压缩路径的时候就省事么?反正内存大,拿空间换时间吧...嘿嘿 那个排序...主要是因为书上的图,当权值一样时都是选择序号较小的始节点构成的边...
    Slyar8年前 (2009-06-02)回复
  23. 赞一个先。 不过。。。并查集用按秩合并写起来很累啊,空间也要求更多。。 其实可以考虑合并的时候随机选择A或者B作为子树。。。 另外,边按权值直接排序不就好了=.= 我的代码只有50多行,差不多只有你的一半。。
    Felix0218年前 (2009-06-02)回复
  24. @epile, 真快...
    Slyar8年前 (2009-06-01)回复
  25. 好像是沙发= = 我刚刷新刷出来的 ~
    epile8年前 (2009-06-01)回复