看图轻松理解并查集

推出一个新系列，《看图轻松理解数据结构和算法》，主要使用图片来描述常见的数据结构和算法，轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种 排序 等等几十篇的样子。

并查集

并查集(Disjoint Set)是一种用于处理不相交集合的数据结构，顾名思义，通过它可以对集合进行合并和查询操作，从而实现元素分组的管理。并查集其中一个典型应用就是在无向图中判断任意两个顶点是否连通。

集合

在数学上，集合被定义为由一个或多个确定的元素所构成的整体，简称集(Set)。集合内的对象称为该集合的元素，集合的元素都具有某种相同的性质。比如“成语大全”集合，它就包含一心一意、三心二意等等所有成语。对于集合A，如果元素a是集合A的元素，则称a属于A，记为 ，如果元素b不是集合的元素，则称b不属于A，记为 。

不相交集合

不相交集合是指两个集合没有公共的元素，反之如果两个集合有相同的元素则说明存在交集。对于两个集合A与B，如果 ，即A与B相交为空集，则称A与B不相交。比如{1, 2, 3}集合和{4, 5, 6}集合就是不相交集合。

主要操作

• 初始化操作，把每个元素初始化为一个集合，根节点父节点都为其本身，O(n)时间复杂度。
• 查找操作，查找某个元素所在的集合，集合由根节点表示，时间复杂度最好情况为O(1)，而最坏的情况为O(n)，有一些优化措施。
• 合并操作，将两个元素所在的集合合并为一个集合，合并前需判断两个元素是否属于同一集合，只有属于不同集合才执行合并，时间复杂度最好情况为O(1)，而最坏的情况为O(n)。

实现方案

并查集的实现方案有很多种，常用的实现方式是通过数组来描述树结构，从而实现并查集数据结构。其中每个集合都用一棵树来表示，树的每个节点代表集合中的一个元素，树的结构通过父指针来表示。比如下图，长度为7的数组，数组值为-1的表示自己为根节点，同时也用它代表集合，正数的值表示它的父节点元素的索引。array[1]=2，说明它的父节点是元素2，array[3]=4，说明它的父节点为元素4。

初始化操作

假如有7个元素，初始化操作即是将每个元素初始化为一个集合，用长度为7的数组来表示，数组中每个元素的值都为-1，-1表示自己是根节点，下标值用于表示集合，比如0表示集合0，1表示集合1等等。

合并操作

合并操作即是将两个集合合并到一起，如果要合并下标为1和2的元素，则先分别找这两个元素对应的集合，元素1的集合为1，

元素2的集合为2，

选择元素2作为元素1的父节点，且元素2作为新的集合。此时，元素1和元素2都属于集合2。

同样地，对元素3和元素4进行合并，结果如下，此时，元素3和元素4都属于集合4。

接着对元素1和元素3也进行合并，需要先分别找出元素1和元素3所在的集合，如果属于同一个集合则不必执行合并，反之如果属于不同的集合，则需要执行合并操作。从元素1开始，因为它的值为2，,说明它的父节点是元素2，

所以往元素2继续查找，到达元素2后发现值为-1，说明元素2就是根节点，所以集合2即是元素1所在的集合。

继续找元素3所在的集合，从元素3开始，因为它的值为4，说明它的父节点是元素4，

所以往元素4继续查找，到达元素4后发现值为-1，说明元素4就是根节点，所以集合4即是元素3所在的集合。

两个元素分别属于不同的集合，于是两个集合执行合并操作，原来的集合。选择元素4作为父节点，元素4作为合并后的集合。此时，集合4包含了元素1、2、3、4。

查找操作

查找操作用于查找某个元素所在的集合。如果要查找元素1所在的集合，那么从元素1开始，因为元素1的值为2，所以往元素2继续找，

元素2的值为4，则继续往元素4查找，

元素4的值为-1，说明它是根节点，即是要找的集合，所以元素1属于集合4。

路径压缩

路径压缩主要用于解决合并后树的高度增加的问题，树的高度变高的话查询效率就会变低。比如继续将元素5和元素4合并，结果树就变成如下，此时对于这棵树来说，其实元素1、2、3、4都可以直接指向元素5。

于是就会在执行查询操作的过程中增加一些判断，用于压缩路径，这样当下一次查询时就可以在更矮的树中查询了。比如现在查询元素1，需要从元素1开始，通过元素2，再到元素4，最后才能找到元素5。

而路径压缩会在第一次查询元素1完成后将树调整为如下图，其实逻辑很简单，就是将元素1在查找的过程中走过的元素统统都指向根节点。

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、 mysql 协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇

跟我交流，向我提问：

欢迎关注：