并查集，不就一并和一查？

谁借莪１个温暖的怀抱￠ 2023-01-17 08:00 114阅读 0赞

### 什么是并查集 ###

并查集这种数据结构，可能出现的频率不是那么高，但是还会经常性的见到，其理解学习起来非常容易，通过本文，一定能够轻轻松松搞定并查集！

对于一种数据结构，肯定是有自己的应用场景和特性，那么并查集是处理什么问题的呢？

并查集是一种**树型**的数据结构，用于处理一些**不相交集合（disjoint sets）的合并及查询问题**,常常在使用中以森林来表示。在一些有N个元素的集合应用问题中，我们通常是在**开始时让每个元素构成一个单元素的集合**，然后按一定顺序**将属于同一组的元素所在的集合合并**，其间要**反复查找**一个元素在哪个集合中。其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

你可能还有点迷糊并查集能怎么玩，**看完这篇然后回头看这两个问题**(分别杭电1232和杭电1272)。

问题1：

> 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

这个问题很容易，给定的关系看看需要合并多少次就知道最少的建设道路数量。

问题二：

> 小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。

![2239516c02f7fa41af3e7ad6993d2a0a.png][]

这个问题也很容易了，根据关系集合进行合如果两个元素已经属于一个集合，那就说明不满足要求啦。

### 并查集解析 ###

通过上面介绍，相信你已经清楚并查集就是解决集合中一些元素的合并和查询问题，现在就带你解析这个算法。

初始化

开始时候森林中每个元素没有任何操作，它们之间是相互独立的。我们通常会使用数组来表示这个森林(数组下标对应第几个元素)，在初始化的时候数组中的各个值为**-1**，表示各自自己是一个集合(各自为王)，你可能会问为啥是-1而不是一个其他的数，那是因为用负数可以代表这个元素是某个集合的根，然后它的权值表示集合中元素的个数。

![c35ee51a2d6cd9cc828c3e3ec1bfb8f3.png][]

并 union(int a,int b)

这里合并，并没有你想象的直接合并那么简单，这里**合并是合并a所在的集合和b所在的集合**，但在操作层面a,b可能并不是根节点，所以也要先判断一下。

为了便于理解，这里罗列一下最初操作可能的情况，初始时候各个元素都是独立的集合，那么直接**a指向b**(或者b指向a)即arr\[a\]=b,同时为了表示这个集合有多少个，原本-1的b再次-1.即arr\[b\]=-2.表示以b为父根的集合节点有|-2|个。例如进行union(1,4)，union(5,7)操作之后如图所示：

![940fde247f081057c4500431d1e4c911.png][]

正常情况的union(int a,int b)，假设我们就是a合并到b上，把b当成父集合来看。a、b都可能是叶子节点，也可能是根节点。

此时你可以**先分别找到a,b的父节点**`fa`,`fb`(这个根可能是它自己),**然后合并fa和fb两个节点**，例如上面如果union(1,5)那么其实就是等价union(4,7)。

![c9e2d2f9e1b38fe686f3e91ee20ec12e.png][]

为什么不直接操作a,b而是要找到他们的父亲进行操作?

**原因1**是因为a,b可能是叶子节点，其值是正的表示已经有父亲了，如果直接操作会使其与原来的集合分离开。另外集合中的数量(负数)也不能有效叠加。

![e3a9e2132f8f526ba788d7def910685a.png][]

**原因2**是因为合并的时候如果合并如果a,b是非根节点操作，可能会造成这个树的深度太大，不利于集合a中的查询效率。

![98e2507a2d7146b7f8fb38ecf2c745a6.png][]

查 search(int a)

查询，其实就是查询这个节点的根节点是啥(也称代表元)，这个过程也有点类似递归的过程，叶子节点值如果为正，那么就继续查找这个值得位置的结果，一直到值为负数的时候说明找到根节点，可以直接返回。

不过在查询的过程中可以顺便路径优化，这样在频繁查询能够大大降低时间复杂度。

### 优化 ###

你以为上面的就是并查集的全部？不不不，并查集还有不少需要掌握嘞，估计细心的人可能也会发现一些问题。

**你可能会有疑问：**

如何查看a，b是否在同一个集合？

查看是否在一个集合，只需要查看节点根祖先的结果是否相同即可。因为只有**根的数值是负**的，而其他都是正数表示指向的元素。所以只需要一直寻找直到不为正数进行比较即可！

a,b合并，究竟是a的祖先合并在b的祖先上，还是b的祖先合并在a上？

这里会遇到两种情况，这个选择也是非常重要的。你要弄明白一点：树的高度+1的化那么整个元素查询的效率都会降低！

所以我们通常是：**小树指向大树(或者低树指向高树)，这个使得查询效率能够增加！**

![42a9015b013fb04c5e962b131de6d4b2.png][]

当然，在**高度和数量**的选择上，还需要你自己选择和考虑。

查找途中能不能路径压缩

每次查询，自下向上。当我们**调用递归**的时候，可以顺便压缩路径(将当前数组的值等于递归返回的根节点的值)，我们查找一个元素只需要直接找到它的祖先，所以**当它距离祖先近**那么下次查询就很快。并且压缩路径的代价并不大！

试想一下，如果一个分支的深度为1000，不压缩路径那么这个分支每个节点平均查找次数为500，压缩一次下次再查找就是1次。

学会路径压缩，你基本可以秒杀大部分并查集的题。

![98249bd89a40f2672b09908e8bf3101d.png][]

### 代码实现 ###

并查集实现起来较为简单，直接贴代码！代码很久前写的，如果有纰漏还请指出。

import java.util.Scanner;
    public class DisjointSet {
        static int tree[]=new int[100000];//假设有500个值
        public DisjointSet()    {set(this.tree);}
        public DisjointSet(int tree[]) 
        {
            this.tree=tree;
            set(this.tree);
        }
      //初始化所有都是-1 有两个好处，这样他们指向-1说明是自己，
      //第二，-1代表当前森林有-（-1）个
        public void set(int a[])
        {
            int l=a.length;
            for(int i=0;i<l;i++)
            {
                a[i]=-1;
            }
        }
        public int search(int a)//返回头节点的数值
        {
            if(tree[a]>0)//说明是子节点
            {
                return tree[a]=search(tree[a]);//路径压缩
            }
            else
                return a;
        }
        public int value(int a)//返回a所在树的大小（个数）
        {
            if(tree[a]>0)
            {
                return value(tree[a]);
            }
            else
                return -tree[a];
        }
        public void union(int a,int b)//表示 a，b所在的树合并
        {
            int a1=search(a);//a根
            int b1=search(b);//b根
            if(a1==b1) {System.out.println(a+"和"+b+"已经在一棵树上");}
            else {
            if(tree[a1]<tree[b1])//这个是负数，为了简单减少计算，不在调用value函数
            {
                tree[a1]+=tree[b1];//个数相加  注意是负数相加
                tree[b1]=a1;       //b树成为a的子树，直接指向a；
            }
            else
            {
                tree[b1]+=tree[a1];//个数相加  注意是负数相加
                tree[a1]=b1;       //b树成为a的子树，直接指向a；
            }
            }
        }
        public static void main(String[] args)
        {       
            DisjointSet d=new DisjointSet();
            d.union(1,2);
            d.union(3,4);
            d.union(5,6);
            d.union(1,6);
    
            d.union(22,24);
            d.union(3,26);
            d.union(36,24);
            System.out.println(d.search(6));    //头
            System.out.println(d.value(6));     //大小
            System.out.println(d.search(22));   //头
            System.out.println(d.value(22));     //大小
        }
    }

### 结语 ###

并查集属于简单但是很高效率的数据结构。在**集合中经常会遇到**。如果不采用并查集而传统暴力效率太低，而不被采纳。

另外，并查集还广泛用于迷宫游戏中，下面有机会可以介绍用并查集实现一个**走迷宫小游戏**。大家欢迎关注！

**推荐阅读**：

[**(加强版)大数加减乘除，一文彻底搞定**][Link 1]

[**花5分钟看这篇之前,你才发现你不懂RESTful**][5_RESTful]

**[Java自学方法和路线，我万字推荐你这样学][Java]**

**[ ][Link 2][栈，就后进先出？][Link 3]**

相互吹捧，共同进步，欢迎关注我的公众号：【bigsai】欢迎**加个好友【q1315426911】**交流，也可**拉你进群交流学习**，也可做个朋友圈点赞之交！如果感觉有收获还请**点赞、在看、分享**一波！

各位xdm希望能点个**一键三连**，小big在这里感激不尽

[2239516c02f7fa41af3e7ad6993d2a0a.png]: /images/20221021/d41006cf0d1a4b3fbd457fbb9ff230cb.png
[c35ee51a2d6cd9cc828c3e3ec1bfb8f3.png]: /images/20221021/f1db775fbf34485db53b1b33e105e79d.png
[940fde247f081057c4500431d1e4c911.png]: /images/20221021/abbaa418a10a482cacfe5805b3665944.png
[c9e2d2f9e1b38fe686f3e91ee20ec12e.png]: /images/20221021/a643fac152204526afffbfdcd6d533a9.png
[e3a9e2132f8f526ba788d7def910685a.png]: /images/20221021/6eefb46afed44beb920223e220e693c2.png
[98e2507a2d7146b7f8fb38ecf2c745a6.png]: /images/20221021/af9a453bd4b84a1387adad975bcc2a9c.png
[42a9015b013fb04c5e962b131de6d4b2.png]: /images/20221021/7d92b35c037c41cb8e5d5cdd15b33856.png
[98249bd89a40f2672b09908e8bf3101d.png]: /images/20221021/8f374c1ec40844c1a25b14792f614f60.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzk0MDIxNjU3OA%3D%3D&chksm=c2e45461f593dd772d36d38dba15850abec39d37cb618cfe54d4e6dd03edbbc43a84a73b9887&idx=1&mid=2247486476&scene=21&sn=7b18d2ab62950ec22eb440b3f32369cf#wechat_redirect
[5_RESTful]: http://mp.weixin.qq.com/s?__biz=Mzg2MTE1NjA2Mg%3D%3D&chksm=ce1a2f43f96da6554a60ab9ce7f37ad26992ed2b9791693dd4d7e50fb7efc44e88ac77b3e2c0&idx=1&mid=2247485682&scene=21&sn=e7959e1367394eb6f3a8fe37aa109cb1#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=Mzk0MDIxNjU3OA%3D%3D&chksm=c2e4539af593da8c5759ec9444e742d4d77bfc3e2ddcae03a68ded425aa1e7f1057768b1047f&idx=1&mid=2247486455&scene=21&sn=e7421f881d97cee9d4fae96638f8306a#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=Mzg2MTE1NjA2Mg%3D%3D&chksm=ce1a2d19f96da40f807426a7322e9a40e6736664e90ab412a0edeaee20dffba0fb7a3637b711&idx=1&mid=2247486120&scene=21&sn=05cf27f6d569a86030f6bef894ee7f7f#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=Mzk0MDIxNjU3OA%3D%3D&chksm=c2e45445f593dd531eb49e6738262dc0d3128ff7f1e35df0a0e75ad5a488ee22eccdef5a355e&idx=1&mid=2247486504&scene=21&sn=8c77bac6efd46baf62bbfb2a34f71738#wechat_redirect