并查集基础

曾经终败给现在 2024-03-16 23:18 56阅读 0赞

#### 一、概念及其介绍 ####

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。

并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。

#### 二、适用说明 ####

并查集用在一些有 **N** 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这个过程看似并不复杂，但数据量极大，若用其他的数据结构来描述的话，往往在空间上过大，计算机无法承受，也无法在短时间内计算出结果，所以只能用并查集来处理。

#### 三、并查集的基本数据表示 ####

![ab03faad27daf2930612a822622b8ae3.png][]

如上图 **0-4** 下面都是 **0**，**5-9** 下面都是 **1**，表示 **0、1、2、3、4** 这五个元素是相连接的，**5、6、7、8、9** 这五个元素是相连的。

![bf8231d9db15e72ffb8033fbf768f1b1.png][]

再如上图 **0、2、4、6、8** 下面都是 **0** 这个集合，表示 **0、2、4、6、8** 这五个元素是相连接的，**1、3、5、7、9** 下面都是 **1** 这个集合，表示 **0，1、3、5、7、9** 这五个元素是相连的。

构造一个类 UnionFind，初始化, 每一个id\[i\]指向自己, 没有合并的元素：

> ...  
> public UnionFind1(int n) \{  
> count = n;  
> id = new int\[n\];  
> // 初始化, 每一个id\[i\]指向自己, 没有合并的元素  
> for (int i = 0; i < n; i++)  
> id\[i\] = i;  
> \}  
> ...

#### Java 实例代码 ####

### UnionFind.java 文件代码： ###

> package runoob.union;  
>   
> public class UnionFind\{  
> private int\[\] id;  
> // 数据个数  
> private int count;  
>   
> public UnionFind1(int n) \{  
> count = n;  
> id = new int\[n\];  
> for (int i = 0; i < n; i++)  
> id\[i\] = i;  
> \}  
>   
> \}

[ab03faad27daf2930612a822622b8ae3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5e87001b92cf4f1981772a5237c1d812.png
[bf8231d9db15e72ffb8033fbf768f1b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6fa3920b7b044c8285c4a67365790eb4.png