并查集快速合并（Java 实例代码）

拼搏现实的明天。 2023-10-14 21:07 43阅读 0赞

**目录**

并查集快速合并

Java 实例代码

UnionFind2.java 文件代码：

--------------------

## 并查集快速合并 ##

对于一组数据，并查集主要支持两个动作：

*  union(p,q) - 将 p 和 q 两个元素连接起来。
 *  find(p) - 查询 p 元素在哪个集合中。
 *  isConnected(p,q) - 查看 p 和 q 两个元素是否相连接在一起。

在上一小节中，我们用 **id** 数组的形式表示并查集，实际操作过程中查找的时间复杂度为 **O(1)**，但连接效率并不高。

本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个节点并且指向自己的父节点，根节点指向自己。如下图所示，节点 3 指向节点 2，代表 3 和 2 是连接在一起的，节点2本身是根节点，所以指向自己。

![0eaff4abe708edb1c4ccb073435b4cf4.png][]

同样用数组表示并查集，但是下面一组元素用 **parent** 表示当前元素指向的父节点，每个元素指向自己，都是独立的。

![502a87cfa071533d4e522a92380ad148.png][]

![31bcc36aa1bd6f328576513780cca5b6.png][]

如果此时操作 union(4,3)，将元素 4 指向元素 3：

![e2ac0ffc77b6be45caa3de502dff8e1e.png][]

数组也进行相应改变：

![4ffe9667dd5d1504c7a1a0867e47bd17.png][]

判断两个元素是否连接，只需要判断根节点是否相同即可。

如下图，节点 4 和节点 9 的根节点都是 8，所以它们是相连的。

![8e3785cecfeaef04688311e354a3a3d4.png][]

连接两个元素，只需要找到它们对应的根节点，使根节点相连，那它们就是相连的节点。

假设要使上图中的 6 和 4 相连，只需要把 6 的根节点 5 指向 4 的根节点 8 即可。

![82b6a5d96df1a4bd63c1c8dd2bc6d5b6.png][]

构建这种指向父节点的树形结构， 使用一个数组构建一棵指向父节点的树，parent\[i\] 表示 i 元素所指向的父节点。

...  
private int\[\] parent;  
private int count; // 数据个数  
...

查找过程, 查找元素 p 所对应的集合编号，不断去查询自己的父亲节点, 直到到达根节点，根节点的特点 parent\[p\] == p，O(h) 复杂度, h 为树的高度。

...  
private int find(int p)\{  
assert( p >= 0 && p < count );  
while( p != parent\[p\] )  
p = parent\[p\];  
return p;  
\}  
...

合并元素 p 和元素 q 所属的集合，分别查询两个元素的根节点，使其中一个根节点指向另外一个根节点，两个集合就合并了。这个操作是 O(h) 的时间复杂度，h 为树的高度。

public void unionElements(int p, int q)\{  
int pRoot = find(p);  
int qRoot = find(q);  
if( pRoot == qRoot )  
return;  
parent\[pRoot\] = qRoot;  
\}

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

**源码包下载：**[Download][]

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

package runoob.union;  
/\*\*  
\* 第二版unionFind  
\*/  
public class UnionFind2 \{  
// 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树  
// parent\[i\]表示第一个元素所指向的父节点  
private int\[\] parent;  
private int count; // 数据个数  
// 构造函数  
public UnionFind2(int count)\{  
parent = new int\[count\];  
this.count = count;  
// 初始化, 每一个parent\[i\]指向自己, 表示每一个元素自己自成一个集合  
for( int i = 0 ; i < count ; i ++ )  
parent\[i\] = i;  
\}  
// 查找过程, 查找元素p所对应的集合编号  
// O(h)复杂度, h为树的高度  
private int find(int p)\{  
assert( p >= 0 && p < count );  
// 不断去查询自己的父亲节点, 直到到达根节点  
// 根节点的特点: parent\[p\] == p  
while( p != parent\[p\] )  
p = parent\[p\];  
return p;  
\}  
// 查看元素p和元素q是否所属一个集合  
// O(h)复杂度, h为树的高度  
public boolean isConnected( int p , int q )\{  
return find(p) == find(q);  
\}  
// 合并元素p和元素q所属的集合  
// O(h)复杂度, h为树的高度  
public void unionElements(int p, int q)\{  
int pRoot = find(p);  
int qRoot = find(q);  
if( pRoot == qRoot )  
return;  
parent\[pRoot\] = qRoot;  
\}  
\}

[0eaff4abe708edb1c4ccb073435b4cf4.png]: https://img-blog.csdnimg.cn/img_convert/0eaff4abe708edb1c4ccb073435b4cf4.png
[502a87cfa071533d4e522a92380ad148.png]: https://img-blog.csdnimg.cn/img_convert/502a87cfa071533d4e522a92380ad148.png
[31bcc36aa1bd6f328576513780cca5b6.png]: https://img-blog.csdnimg.cn/img_convert/31bcc36aa1bd6f328576513780cca5b6.png
[e2ac0ffc77b6be45caa3de502dff8e1e.png]: https://img-blog.csdnimg.cn/img_convert/e2ac0ffc77b6be45caa3de502dff8e1e.png
[4ffe9667dd5d1504c7a1a0867e47bd17.png]: https://img-blog.csdnimg.cn/img_convert/4ffe9667dd5d1504c7a1a0867e47bd17.png
[8e3785cecfeaef04688311e354a3a3d4.png]: https://img-blog.csdnimg.cn/img_convert/8e3785cecfeaef04688311e354a3a3d4.png
[82b6a5d96df1a4bd63c1c8dd2bc6d5b6.png]: https://img-blog.csdnimg.cn/img_convert/82b6a5d96df1a4bd63c1c8dd2bc6d5b6.png
[Download]: https://www.runoob.com/wp-content/uploads/2020/10/runoob-algorithm-union.zip