并查集实现中的一个小疑难

CodeingBoy 3月 18, 2017

最近阅读《啊哈!算法!》的时候,按照其中的思想实现并查集构造代码的时候,发现了一个疑难:

现在我来给你支个招,嘿嘿( ^_^ )古语云“擒贼先擒王”。你直接找“2 号强盗”的 BOSS“1 号强盗”谈,让其归顺“5 号强盗”就 OK 了,也就是将 f[1] 的值改为 5,如下。

  5 5 3 3 5 6 7 8 9 10
数组f 1 2 3 4 5 6 7 8 9 10

细心的同学们可能会发现一个问题:我不但将 f[1] 的值改为 5,还将f[2] 的值也改为了 5。

 然后我自己实现代码的时候却发现,处理完“5 号强盗”和“2 号强盗”合并的线索后,数组的状态却如下表所示:

  5 1 3 3 5 6 7 8 9 10
数组f 1 2 3 4 5 6 7 8 9 10

f[2] 的值竟然不是 5!是不是出了什么问题?

并处理完所有线索的数组状态如下表:

  5 5 5 5 5 5 8 9 9 10
数组f 1 2 3 4 5 6 7 8 9 10

从数组的数字来看,这应该是有 4 个而不是 3 个集合。是哪里出错了?

难道是进行路径压缩的代码错了? 经过推导,发现并没有错,路径压缩的代码不会对终端节点(也就是 f[2])做出修改。运行书本里面的代码亦是如此。

如果这个状态是正常的话,那么是如何得知集合数的呢?注意 main 函数里面还有这样一段代码:

这才是关键所在。这段代码仅仅会统计无祖先的节点个数,而会无视不同数字的个数。换言之,真正起作用的只是数组中数据的祖先个数,与各节点祖先索引并无关系。路径压缩也并不是必需的,只是提高性能的一种办法而已。

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/%e5%b9%b6%e6%9f%a5%e9%9b%86%e5%ae%9e%e7%8e%b0%e4%b8%ad%e7%9a%84%e4%b8%80%e4%b8%aa%e5%b0%8f%e7%96%91%e9%9a%be/

发表评论

电子邮件地址不会被公开。 必填项已用*标注