概念及其介绍
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林（parent）
- 树的根节点唯一标识了一个集合
- 我们只要找到了某个元素的的树根
- 就能确定它在哪个集合里。
并查集构造方法
public class Union {
int n;
int[] parent;
// size[i] 表示以 i 为根，集合中元素的个数
int[] size;
// rank[i] 表示以 i 为根为集合，所表示的输的层数
int[] rank;
public Union(int n, int[] parent) {
// 表示集合的元素个数
this.n = n;
// 初始化数组
parent = new int[n];
// 填充数组
for (int i = 0; i < n; i++) {
// 这里表示 元素值 i 归属的集合编号 是 i
parent[i] = i;
// 初始化 每一个集合中的元素个数都为1
size[i] = 1;
// 初始化 树的层数 是 1
rank[i] = 1;
}
}
}- 有三个重要概念，分别是 归属集合、集合中元素个数和树的层数
- 归属集合
- 用
parent数组进行表示
- 元素个数
- 用
size数组进行表示
- 树的层数
- 用
rank数组进行表示
- 图例1
- 图例2
- 编号 0 的集合现在只有一个元素就是其本身，层数为 1
- 编号 1 的集合现在有两个元素
{0, 1}，层数为 2
并查集快速查找
- 问题提出：如何查找元素所在的集合编号？
public int find(int val) {
assert val >= 0 && val < n;
// 查找 val 所属的集合编号
return parent[val];
}- 但是这样存在一个问题，如下图
- 如上图示：
find(0) = 1: 表示 0 属于 编号为 1 的集合find(1) = 2: 表示 1 属于 编号为 2 的集合- 然后所有的元素都属于编号为 4 的集合，元素个数为 5，层数为 5
- 所以该种方法无法找到元素最终归属的集合
优化一
查找目标元素所对应的根集合编号
public int find(int val) {
assert val >= 0 && val < n;
while(val != parent[val]) {
val = parent[val];
}
return val;
}- 以下图为例
val = 0 , parent[val] = 1，不相等-令val = 1val = 1 , parent[val] = 2->val = 2val = 2 , parent[val] = 3->val = 3val = 3 , parent[val] = 4->val = 4val = 4 , parent[val] = 4最终返回4：元素 0 所属的集合编号是 4
优化二
优化一中的例子，需要计算 4 次之后才能够找到元素最终归属的集合编号
- 但是实际上，
{0, 1, 2, 3, 4}都同属于 4号集合
- 如下图，
find(0) = 4可以直接得出结果 - 并且对应 层数 发生了变化 从
5 -> 2
- 期望实现达到的效果是 如下图---> 从左到右 的转换
- 代码实现如下
public int find(int val) {
assert val >= 0 && val < n;
while(val != parent[val]) {
// 查找过程中不断更新
parent[val] = find(parent[val]);
}
return val;
}并查集判断两个元素是否相连
public boolean isConnected(int a, int b) {
return find(a) == find(b);
}- 判断两个元素是否相连的方法较为简单
- 直接利用find方法即可
并查集合并
并查集合并的相关代码和find方法的相关代码相关
路径优化
package new_start.classic;
/**
* desc : 并查集--rank优化
* <p>
* create time : 2023/10/14 21:26
*/
public class UnionRankBest {
int n;
int[] parent;
// 记录每一个集合的层数
int[] rank;
public UnionRankBest(int n) {
this.n = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
// 初始化 rank[i] = 1
rank[i] = 1;
}
}
public int find(int val) {
assert val >= 0 && val < n;
while (val != parent[val]) {
val = parent[val];
}
return val;
}
public boolean isConnected(int a, int b) {
return find(a) == find(b);
}
public void union(int a, int b) {
// 拿到 a b 所属的集合编号
int rA = find(a);
int rB = find(b);
if (rA == rB) {
// 同属于一个集合
return;
}
if (rank[rA] < rank[rB]) {
// a 的层数低
parent[rA] = rB;
} else if (rank[rA] > rank[rB]) {
// 层数低 的 指向层数 高的，rank 不变
parent[rB] = rA;
} else {
// rank[rA] == rank[rB]
parent[rA] = rB;
rank[rB] += 1;
}
}
}size优化
package new_start.classic;
/**
* desc : 并查集 size 优化
* <p>
* create time : 2023/10/14 21:39
*/
public class UnionSizeBest {
int n;
int[] parent;
int[] size;
public UnionSizeBest(int n) {
this.n = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int v) {
assert v >= 0 && v < n;
while (v != parent[v]) {
v = parent[v];
}
return v;
}
public boolean isConnected(int a, int b) {
return find(a) == find(b);
}
public void union(int a, int b) {
int rA = find(a);
int rB = find(b);
if (rA == rB) {
return;
}
if (size[rA] < size[rB]) {
// 如果 a 所属集合的元素比 b 少
// 那么 将 元素少的集合 指向元素多的集合进行合并
parent[rA] = rB;
size[rB] += size[rA];
} else {
// a 集合的元素多
parent[rB] = rA;
size[rA] += size[rB];
}
}
}路径压缩
package new_start.classic;
/**
* desc : 并查集--路径压缩
* <p>
* create time : 2023/10/14 21:26
*/
public class UnionRankCompress {
int n;
int[] parent;
public UnionRankCompress(int n) {
this.n = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int val) {
assert val >= 0 && val < n;
while (val != parent[val]) {
// 查找并更新，减少 树的层数
parent[val] = find(parent[val]);
}
return val;
}
public boolean isConnected(int a, int b) {
return find(a) == find(b);
}
public void union(int a, int b) {
// 拿到 a b 所属的集合编号
int rA = find(a);
int rB = find(b);
if (rA == rB) {
// 同属于一个集合
return;
}
// a 所属集合 指向 b 所属集合，这个时候 经过 find 方法，层数为 2
parent[rA] = rB;
}
}