并查集
并查集分为Quick_Find和Quick_Union两种方式。
定义一个抽象类
abstract public class UnionFind {
int[] parent;
protected UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("参数小于0");
}
parent = new int[capacity];
// 初始化时每一个节点都指向自己
for (int i = 0; i < capacity; i++) {
parent[i] = i;
}
}
// 查询根节点
abstract public int find(int n);
// 合并两块区域
abstract public void union(int v1, int v2);
// 判断两个节点是否有相同的根节点
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
}
}
两种并查集的实现方式
quick_find
查询复杂度为O(1),合并复杂度为O(n),本质是将节点的都指向父节点,使得生成的树高度为1。
如图:
// 查询方法实现
public int find(int n) {
return parent[n];
}
// 合并方法实现
public void union(int v1, int v2) {
// 查询两个节点的根节点
int l = parent[v1];
int r = parent[v2];
if (l == r) return;
// 将左边节点的父节点拆开,都放到右边的父节点上
for (int i = 0; i < parent.length; i++) {
if (parent[i] == l) {
parent[i] = r;
}
}
}
quick_union
查询时间复杂度为O(log n),合并时间复杂度也为O(log n),本质是左节点的根节点指向右节点的根节点。
如图:
// 查询方法实现
public int find(int n) {
// 一层一层找,直到找到根节点
while (n != parent[n]) {
n = parent[n];
}
return n;
}
// 合并方法实现
public void union(int v1, int v2) {
// 找到两个节点的根节点
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
// 将左边的根节点的父节点指向右边根节点
parent[p1] = p2;
}
上面的实现方式可能会导致树过于高,甚至会成为链表形式,有两种优化方式:
- 将节点少的嫁接到节点多的根节点上
如图:
public class QuickUnion_S1 extends QuickUnion {
// 定义一个size数组,定义节点所属的根节点有多少节点
private int[] sizes;
public QuickUnion_S1(int capacity) {
super(capacity);
sizes = new int[capacity];
// 初始化时每一个节点都为1
for (int i = 0; i < capacity; i++) {
sizes[i] = 1;
}
}
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
// 判断两个根节点下的有多少子节点
// 少的根节点嫁接到多的根节点上
if (sizes[p1] < sizes[p2]) {
parent[p1] = p2;
sizes[p2] += sizes[p1];
}else {
parent[p2] = p1;
sizes[p1] += sizes[p2];
}
}
}
- 将树低的嫁接到树高的根节点上
public class QuickUnion_S2 extends QuickUnion {
// 定义一个rank数组记录节点的根节点的树高
private int[] ranks;
public QuickUnion_S2(int capacity) {
super(capacity);
ranks = new int[capacity];
// 每一个树高都是1
for (int i = 0; i < capacity; i++) {
ranks[i] = 1;
}
}
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
//判断两个树的高度
// 将树低的根节点指向树高的根节点
if (ranks[p1] < ranks[p2]) {
parent[p1] = p2;
} else if (ranks[p2] < ranks[p1]) {
parent[p2] = p1;
} else {
// 如果相同,因为多了根节点多了根节点,可以导致树高多一层
parent[p1] = p2;
// 被指向的根节点树高加一
ranks[p2]++;
}
}
}
路径压缩
对quick_union优化后,树高的增长速度会慢一些,但是还是会不断增加其高度,所以可以在查询时降低树的高度,调节树的结构,有三种实现方式:
- 普通路径压缩 --> 所有节点在查询时,都指向其根节点
@Override
public int find(int n) {
// 如果不是根节点
if (parent[n] != n){
// 查询其父节点的父节点,并赋予当前父节点
parent[n] = find(parent[n]);
}
return parent[n];
}
该种方法使得结构变化太大,会导致查询速度慢很多,下面两种结构变化相对慢一些
- 路径分裂 --> 每个节点都指向其祖父节点
@Override
public int find(int n) {
while (n != parent[n]) {
int p = parent[n];
parent[n] = parent[parent[n]];
n = p;
}
return n;
}
- 路径减半 --> 每隔一个节点指向其祖父节点
@Override
public int find(int n) {
while (n != parent[n]){
parent[n] = parent[parent[n]];
n = parent[n];
}
return n;
}