概念
并查集 (union & find) 是⼀种树型的数据结构，⽤于处理⼀些不交集(Disjoint Sets)的合并及查询问题。
两种操作方式：
-
Find: 确定元素属于哪⼀个⼦集。它可以被⽤来确定两个元素是否 属于同⼀子集。
-
Union: 将两个⼦集合并成同⼀个集合。
比如：我们判断c,f是否在同一个集合中，以及将上述两个集合合并为一个集合。 -
在⽣活中的例例⼦子
- ⼩弟 —> ⽼大
- 帮派识别
时间复杂度
也就是：经过优化后的代码，时间复杂度为 O(5) 。
如何代码实现
一般内部使用数组实现
public class UF {
private int[] roots;
public UF(int n) {
roots = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
}
}
// 确定元素属于哪⼀个⼦集，返回 集合 的老大
public int find(int x) {
if (roots[x] == x) {
return x;
}
return find(roots[x]);
}
// 将两个⼦集合并成同⼀个集合
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
// x 集合的老大归属了 y 集合的老大
roots[xRoot] = yRoot;
}
public static void main(String[] args) {
UF uf = new UF(100);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
System.out.println(uf.find(1));
System.out.println(uf.find(2));
System.out.println(uf.find(3));
System.out.println(uf.find(4));
System.out.println(uf.find(5));
}
}
输出结果是：
3
3
3
5
5
Process finished with exit code 0
上述构造出来的结构是：
两种优化手段
根据 Rank 进行优化
看图，上面两个集合，合并的话会存在下面的两种方式，很明显，第二种合并方式要好的多。具体的实现就是：保存一个Rank（树高），在每次合并的时候，总是树低的往树高的合并
示例 PY 代码：
路径压缩优化
还是看图，很明显，我们在使用并查集时，并不关注集合本身到底长什么样子，而关注的是 什么元素在什么集合中，所以就可以做出如下优化。
核心逻辑列在这里：
public class UFUpgrade {
private int[] roots;
// 即：树高
private int[] rank;
public UFUpgrade(int n) {
roots = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
rank[i] = 1;
}
}
// 确定元素属于哪⼀个⼦集，返回 集合 的老大
public int find(int x) {
while (x != roots[x]) {
roots[x] = roots[roots[x]];
rank[x] -= 1;
x = roots[x];
}
return x;
}
// 将两个⼦集合并成同⼀个集合
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
// 相交, 跳过
if (xRoot == yRoot) {
return;
}
// 在每次合并的时候，总是树低的往树高的合并
if (rank[xRoot] < rank[yRoot]) {
// x 集合的老大归属了 y 集合的老大
roots[xRoot] = yRoot;
rank[xRoot] += 1;
} else {
roots[yRoot] = xRoot;
rank[yRoot] += 1;
}
}
public static void main(String[] args) {
UFUpgrade uf = new UFUpgrade(10);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
for (int i = 0; i < 5; i++) {
System.out.print(uf.roots[i]);
}
System.out.println();
System.out.println(uf.find(1));
System.out.println(uf.find(2));
System.out.println(uf.find(3));
System.out.println(uf.find(4));
System.out.println(uf.find(5));
}
}