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

梦里梦外; 2023-10-14 21:06 48阅读 0赞

**目录**

并查集快速查找

Java 实例代码

UnionFind1.java 文件代码：

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

## 并查集快速查找 ##

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。

查询元素所在的集合编号，直接返回 **id** 数组值，**O(1)** 的时间复杂度。

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

合并元素 **p** 和元素 **q** 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 **O(n)** 复杂度。

...  
public void unionElements(int p, int q) \{  
int pID = find(p);  
int qID = find(q);  
if (pID == qID)  
return;  
for (int i = 0; i < count; i++)  
if (id\[i\] == pID)  
id\[i\] = qID;  
\}  
...

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

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

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

package runoob.union;  
  
/\*\*  
\* 第一版union-Find  
\*/  
public class UnionFind1 \{  
// 我们的第一版Union-Find本质就是一个数组  
private int\[\] id;  
// 数据个数  
private int count;  
  
public UnionFind1(int n) \{  
count = n;  
id = new int\[n\];  
// 初始化, 每一个id\[i\]指向自己, 没有合并的元素  
for (int i = 0; i < n; i++)  
id\[i\] = i;  
\}  
  
// 查找过程, 查找元素p所对应的集合编号  
private int find(int p) \{  
assert p >= 0 && p < count;  
return id\[p\];  
\}  
  
// 查看元素p和元素q是否所属一个集合  
// O(1)复杂度  
public boolean isConnected(int p, int q) \{  
return find(p) == find(q);  
\}  
  
// 合并元素p和元素q所属的集合  
// O(n) 复杂度  
public void unionElements(int p, int q) \{  
  
int pID = find(p);  
int qID = find(q);  
  
if (pID == qID)  
return;  
  
// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并  
for (int i = 0; i < count; i++)  
if (id\[i\] == pID)  
id\[i\] = qID;  
\}  
\}

[Download]: https://www.runoob.com/wp-content/uploads/2020/10/runoob-algorithm-union.zip