并查集也叫作不相交集合(Disjoint Set)
并查集有2个核心操作
- (Find):查找元素所在的集合(这里的集合并不是特指Set这种数据结构，是指广义的数据集合)
- 合并(Union):将两个元素所在的集合合并为一个集合
有2种常见的实现思路
- Quick Find
✓ 查找(Find)的时间复杂度:O(1)
✓ 合并(Union)的时间复杂度:O(n) - Quick Union
✓查找(Find)的时间复杂度:O(logn)，可以优化至 O(𝛼(𝑛)) ，α(𝑛) < 5
✓合并(Union)的时间复杂度:O(logn)，可以优化至 O(𝛼(𝑛)) ，α(𝑛) < 5
UnionFind.java
public abstract class UnionFind {
protected int[] parents;
public UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity must be >= 1");
}
parents = new int[capacity];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}
/**
* 查找v所属的集合（根节点）
* @param v
* @return
*/
public abstract int find(int v);
/**
* 合并v1、v2所在的集合
*/
public abstract void union(int v1, int v2);
/**
* 检查v1、v2是否属于同一个集合
*/
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
}
protected void rangeCheck(int v) {
if (v < 0 || v >= parents.length) {
throw new IllegalArgumentException("v is out of bounds");
}
}
}
UnionFind_QF.java
public class UnionFind_QF extends UnionFind {
public UnionFind_QF(int capacity) {
super(capacity);
}
/*
* 父节点就是根节点
*/
public int find(int v) {
rangeCheck(v);
return parents[v];
}
/**
* 将v1所在集合的所有元素，都嫁接到v2的父节点上
*/
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
for (int i = 0; i < parents.length; i++) {
if (parents[i] == p1) {
parents[i] = p2;
}
}
}
}
UnionFind_QU.java
public class UnionFind_QU extends UnionFind {
public UnionFind_QU(int capacity) {
super(capacity);
}
/**
* 通过parent链条不断地向上找，直到找到根节点
*/
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
v = parents[v];
}
return v;
}
/**
* 将v1的根节点嫁接到v2的根节点上
*/
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
parents[p1] = p2;
}
}
UnionFind_QU_R.java
/**
* Quick Union - 基于rank的优化
*/
public class UnionFind_QU_R extends UnionFind_QU {
private int[] ranks;
public UnionFind_QU_R(int capacity) {
super(capacity);
ranks = new int[capacity];
for (int i = 0; i < ranks.length; i++) {
ranks[i] = 1;
}
}
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (ranks[p1] < ranks[p2]) {
parents[p1] = p2;
} else if (ranks[p1] > ranks[p2]) {
parents[p2] = p1;
} else {
parents[p1] = p2;
ranks[p2] += 1;
}
}
}
UnionFind_QU_S.java
/**
* Quick Union - 基于size的优化
*/
public class UnionFind_QU_S extends UnionFind_QU {
private int[] sizes;
public UnionFind_QU_S(int capacity) {
super(capacity);
sizes = new int[capacity];
for (int i = 0; i < sizes.length; i++) {
sizes[i] = 1;
}
}
/**
* 将v1的根节点嫁接到v2的根节点上
*/
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (sizes[p1] < sizes[p2]) {
parents[p1] = p2;
sizes[p2] += sizes[p1];
} else {
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}
}
UnionFind_QU_R_PC.java
/**
* Quick Union - 基于rank的优化 - 路径压缩(Path Compression)
*
*/
public class UnionFind_QU_R_PC extends UnionFind_QU_R {
public UnionFind_QU_R_PC(int capacity) {
super(capacity);
}
@Override
public int find(int v) { // v == 1, parents[v] == 2
rangeCheck(v);
if (parents[v] != v) {
parents[v] = find(parents[v]);
}
return parents[v];
}
}
UnionFind_QU_R_PH.java
/**
* Quick Union - 基于rank的优化 - 路径减半(Path Halving)
*
*/
public class UnionFind_QU_R_PH extends UnionFind_QU_R {
public UnionFind_QU_R_PH(int capacity) {
super(capacity);
}
@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
}
UnionFind_QU_R_PS.java
/**
* Quick Union - 基于rank的优化 - 路径分裂(Path Spliting)
*
*/
public class UnionFind_QU_R_PS extends UnionFind_QU_R {
public UnionFind_QU_R_PS(int capacity) {
super(capacity);
}
@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
int p = parents[v];
parents[v] = parents[parents[v]];
v = p;
}
return v;
}
}
泛型的并查集 GenericUnionFind.java
public class GenericUnionFind<V> {
private Map<V, Node<V>> nodes = new HashMap<>();
public void makeSet(V v) {
if (nodes.containsKey(v)) return;
nodes.put(v, new Node<>(v));
}
/**
* 找出v的根节点
*/
private Node<V> findNode(V v) {
Node<V> node = nodes.get(v);
if (node == null) return null;
while (!Objects.equals(node.value, node.parent.value)) {
node.parent = node.parent.parent;
node = node.parent;
}
return node;
}
public V find(V v) {
Node<V> node = findNode(v);
return node == null ? null : node.value;
}
public void union(V v1, V v2) {
Node<V> p1 = findNode(v1);
Node<V> p2 = findNode(v2);
if (p1 == null || p2 == null) return;
if (Objects.equals(p1.value, p2.value)) return;
if (p1.rank < p2.rank) {
p1.parent = p2;
} else if (p1.rank > p2.rank) {
p2.parent = p1;
} else {
p1.parent = p2;
p2.rank += 1;
}
}
public boolean isSame(V v1, V v2) {
return Objects.equals(find(v1), find(v2));
}
private static class Node<V> {
V value;
Node<V> parent = this;
int rank = 1;
Node(V value) {
this.value = value;
}
}
}
网友评论