Blog·Tanky WooABOUTRSS

《算法导论》学习总结 — 第21章 用于不相交集合的数据结构

09 Nov 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

并查集(Disjoint Set)

起因:在某些应用中,要将n个不同的元素分成一组不相交的集合。

第21.1节 不相交集合的链表表示有些不太明白,有达人讲解或贡献出自己的学习笔记????

启发式策略是什么?--->我对这个概念一直很好奇???但是一直找不到好的文章和解释,看到我文章的朋友,求推荐,谢谢。

21.3节 不相交集合森林

这个曾经写过一个模板,书看了后,基本都可以写出来吧,依葫芦画瓢,代码模板链接:

http://www.wutianqi.com/?p=1066

至于两种启发式策略,来分别说下其作用:

①.按秩合并(union by rank),把较少结点的树的根合并到较多结点的树的跟,这样是为了尽量使树的高度减小,因此,可以优化FindSet(x)。(看FindSet()函数的代码~~)

②.路径压缩(path compression),使查找路径上的每个结点都指向根节点,路径压缩并不改变结点的秩,而且这样也同样优化了Find_Set(x)。

完毕!