一、定义
并查集(Union Find)是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(动态连通性问题),常常在使用中以森林来表示。
1-1 动态连通性动态连通性
对于一系列整数,其中每个整数都表示一种类型的对象,一对整数p和q可以被理解为“p和q是相连的”。我们假设“相连”是一种对等的关系,这意味着“相连”具有以下性质:
①自反性:p和p是相连的;
②对称性:如果p和q是相连的,那么q和p也是相连的;
③传递性:如果p和q是相连的,q和r是相连的,那么p和r也是相连的。
并查集API定义:
注:union方法用于将两个分量合并;find方法返回指定触点所在的连通分量标识
二、实现
基于加权和路径压缩的并查集算法:
1. 加权:
用一个数组保存当前各个连通分量的高度(权重),初始时都为1。
每次归并时,将权重小的连通分量接到权重大的连通分量上,同时权重加1。
2. 路径压缩:
每次查找一个触点的所属的连通分量标识(根结点)时,将所有路径上遇到的触点直接链接到根节点。
2-2 算法轨迹(不含压缩路径)
源码:
public class WeightedQuickUnionPathCompressionUF {
private int[] parent; // parent[i]:结点i的父亲结点
private int[] size; // size[i]:结点i所在的连通分量权重
private int count; // 连通分量个数
public WeightedQuickUnionPathCompressionUF(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1; // 初始时每个连通分量权重为1
}
}
public int count() {
return count;
}
/**
* 返回结点p所在的连通分量标识
*/
public int find(int p) {
// 查找p的根节点root
while (p != parent[p])
p = parent[p];
int root = p;
// 将所有路径上遇到的触点直接链接到根节点
while (p != root) {
int tmp = parent[p];
parent[p] = root;
p = tmp;
}
return root;
}
/**
* 判断结点p和结点q是否连通
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* 根据权重,将结点p和结点q所在的连通分量合并
* (即将p的根结点和q的根结点连接) 权重相同时, 以p所在连
* 通分量作为连通标识
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 将权重小的连通分量链接到权重大的连通分量上
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
}
三、性能分析
并查集算法有很多种,下图给出了各类并查集算法的比较。
注:本文的实现中采用的是 基于加权和路径压缩的并查集算法 ,时间复杂度接近于O(1)。
网友评论