并查集快速查找-开发文档-JsSaaS开发平台

系统、网站、API站点，简单高效开发

数据结构

数据结构与算法插入排序希尔排序归并排序随机化快速排序双路快速排序三路排序算法排序算法衍生问题

堆

堆的基本存储堆的 shift up 堆的 shift down 基础堆排序优化堆排序索引堆及其优化

二分搜索树

二分搜索树二分搜索树节点的插入二分搜索树节点的查找二分搜索树深度优先遍历二分搜索树层序遍历二分搜索树节点删除二分搜索树的特性

并查集

并查集基础并查集快速查找并查集快速合并并查集 size 的优化并查集 rank 的优化并查集路径压缩

图论

图论基础和表示相邻节点迭代器深度优先遍历与连通分量寻路算法广度优先遍历与最短路径

并查集快速查找

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

查询元素所在的集合编号，直接返回 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;
}
}