需求分析
假设n 个村庄, 有些村庄之间有连接的路, 有些没有
设计一个数据结构, 快速执行2 个操作
- 查询2 个村庄是否有连接的路
- 连接2 个村庄
数组, 链表, 平衡二叉树, 集合, 都可以实现, 查询和连接的复杂度为O(n)
并查集适合解决"连接" 类的问题
连接的均摊时间复杂度都是O(α(n)), α(n) < 5
村庄集合
并查集
也叫不相交集合
查找: 查找元素所在的集合, 广义上的数据集合
合并: 讲两个元素所在的集合合并为一个集合
2 种常见思路
-
Quick Find
查找(Find) 的时间复杂度: O(1)
合并(Union) 的时间复杂度: O(n)
-
Quick Union
查找(Find) 的时间复杂度为O(logn), 可以优化至O(α(n)), α(n) < 5
合并(Union) 的时间复杂度O(logn), 可以优化至O(α(n)), α(n) < 5
并查集可以用数组实现的树形结构
接口抽象类
public abstract class UnionFind {
protected int[] parents;
// 初始化, 每个元素各自属于一个单元素集合
public UnionFind(int capacity) {
if (capacity < 10) {
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);
public abstract void union(int v1, int 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");
}
}
}
初始化
每个元素各自属于一个单元素集合
初始化
Quick Find - Union
QF合并集合
Quick Find - Find
使得所有元素指向另一个的根节点, 时间复杂度O(1)
QF查找集合
/**
* Quick Find
* @author null
*
*/
public class UnionFind_QF extends UnionFind {
public UnionFind_QF(int capacity) {
super(capacity);
}
@Override
public int find(int v) {
rangeCheck(v);
return parents[v];
}
@Override
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;
}
}
}
}
Quick Union - Union
union(v1, v2), v1 的根节点指向v2 的根节点, 复杂度O(logn)
QU合并集合
Quick Union - Find
查找时, 将一个集合的根节点指向另一个集合的根节点, 复杂度O(logn)
public class UnionFind_QU extends UnionFind {
public UnionFind_QU(int capacity) {
super(capacity);
}
/**
* 通过parent 链表不断向找, 直到找到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;
}
}
优化 - Quick -Union
在Union 过程中, 可能出现树不平衡的情况, 退化成链表
QU退化为链表
2 种常见优化方案
- 基于size 优化, 元素少的树嫁接到元素多的树
- 基于rank 优化, 矮的树嫁接到高的树
基于size 的优化
QU基于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;
}
}
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (sizes[p1] < sizes[p2]) {
sizes[p2] += sizes[p1];
} else {
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}
}
但是也会出现不平衡问题
基于rank 优化
树高的嫁接到树矮的情况, 导致find 操作变慢
路径压缩(Path Compression)
在find 时使路径上的所有节点都指向根节点, 从而降低树的高度
QU基于rank路径压缩优化
查找1,0,7
路径压缩使所有节点都指向根节点, 所以实现成本稍高
/**
* 基于ranks 的优化
* @author null
*
*/
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;
}
}
}
继续优化, 使得树的高度降低, 实现成本比路径压缩低
- 路径分裂(Path Spliting)
- 路径减半(Path Halving)
路径分裂, 路径减半, 效率差不多, 但都比路径压缩要好
路径压缩
/**
* Quick Find 基于rank 的哟花 - 压缩路径
* @author null
*
*/
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) {
rangeCheck(v);
if (parents[v] != v) {
parents[v] = find(parents[v]);
}
return parents[v];
}
}
路径分裂(Path Spliting)
使路径上的每个节点都指向其祖父节点
路径分裂
/**
* Quick Find 基于rank 的哟花 - Path Spliting
* @author null
*
*/
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;
}
}
路径减半(Path Halving)
使路径上每隔一个节点就指向其祖父节点
路径减半
/**
* Quick Find 基于rank 的哟花 - Path Halving
* @author null
*
*/
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;
}
}
泛型
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;
}
}
}
