Union Find 并查集
并查集主要支持两个操作：Union(合并分组) 与 Find(查询分组）操作。
什么是并查集？
并查集是一种用于处理一些不交集的合并及查询问题的数据结构。并查集支持如下操作：
Union(合并)：将两个集合合并为一个
Find(查询分组)：查询某个元素属于哪个集合，也可判断两个元素是否位于同一个集合
isConnected: 判断两个元素是否属于同一个集合，借用Find 操作完成
比如公司里面每一个人都有一个工号，判断两个员工是否位于同一个部门 就可以使用并查集里面的 Find 操作。将某位员工调往另外一个部门就可以使用 Union 操作。
并查集的实现
首先定义一个接口：
public interface IUF {
boolean isConnected(int p, int q);
void unionElements(int p, int q);
int getSize();
}第一个版本的并查集
并查集的最基础的实现方法非常简单，用一个数组就可以完成。数组的索引是独一无二的，用于标识不同的元素，数组内的值用来表示所属的集合。
Find 与 Union 操作
用这种实现方式，Find 操作非常简单，直接返回判断两个数组元素是否相等即可。Union操作也非常简单，遍历一边数组，将需要合并的两个元素所对应的两个集合内的所有元素都设置成一样，即可完成合并两个集合的目的。完整代码如下：
//第一版并查集
//union O(n)
//isConnected(p,q) O(1)
public class UnionFind1 implements IUF{
private int[] group;
public UnionFind1(int size){
group=new int[size];
for (int i = 0; i < group.length; i++) {
group[i]=i;
}
}
private int find(int p){
if (p<0 || p>=group.length){
System.out.println(p);
throw new IllegalArgumentException("Index is out of bound!");
}
return group[p];
}
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pID=find(p);
int qID=find(q);
if (pID == qID) {
return;
}
for (int i = 0; i < group.length; i++) {
if (group[i]==pID){
group[i]=qID;
}
}
}
@Override
public int getSize() {
return group.length;
}
}第二个版本的并查集
将每个元素看成一个节点，同时每个节点指向它的父节点，根节点指向自己，根节点的元素即为整个集合的类别。同样也可以用一个数组就可以完成。数组的索引是独一无二的，用于标识不同的元素，数组内的值用来表示元素的父节点。一开始将数组内的元素设置为与索引相同，表示所有元素都属于不同的集合。
当
Find 与 Union 操作
当进行Find 操作时, 只需要找到该节点的祖先节点即可完成。当进行Union 操作时, 只需要将一个元素的祖先节点指向另一个节点的祖先节点即可。如下图，需要将6 节点所在的集合与3节点所在的集合进行合并，只需要将3节点的祖先节点，也就是0节点，指向3节点的祖先节点，也就是1节点，即可实现两个集合的合并。
完整代码如下：
//第二版并查集
//union O(n) O(h),h为树的高度
//isConnected(p,q) O(h),h为树的高度
public class UnionFind2 implements IUF{
private int[] parent;
public UnionFind2(int size){
parent=new int[size];
for (int i=0;i<size;i++){
parent[i]=i;
}
}
//查询p的根节点,O(h)复杂度,h为树的高度
private int find(int p){
if (p<0 || p>=parent.length){
throw new IllegalArgumentException("Index is out of bound!");
}
while (p!=parent[p]){
p=parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if ( pRoot==qRoot ){
return;
}
parent[pRoot]=qRoot;
}
@Override
public int getSize() {
return parent.length;
}
}
第三个版本的并查集
在第二版本的基础上，使用 size 优化，也就是在Union 操作时，节点数较小的树指向节点数较大的树。之所以这样优化是假设一棵大树与一棵小树进行合并时，如果是大树指向小树，那么需要找到大树的根节点，而大树的根节点通常深度较高，操作起来更费时。为此，需要额外的一个 sz 数组，用来存储树的节点个数。
完整代码如下：
//第三版并查集, union过程基于size优化, 小树指向大树
//union O(n) O(h),h为树的高度
//isConnected(p,q) O(h),h为树的高度
public class UnionFind3 implements IUF{
private int[] parent;
private int[] sz;// sz[i]表示以i为根的树的个数
public UnionFind3(int size){
parent=new int[size];
sz=new int[size];
for (int i=0;i<size;i++){
parent[i]=i;
sz[i]=1;
}
}
//查询p的根节点,O(h)复杂度,h为树的高度
private int find(int p){
if (p<0 || p>=parent.length){
throw new IllegalArgumentException("Index is out of bound!");
}
while (p!=parent[p]){
p=parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if ( pRoot==qRoot ){
return;
}
if (sz[pRoot]<sz[qRoot]){
parent[pRoot]=qRoot;
sz[qRoot]+=sz[pRoot];
}else {
parent[qRoot]=pRoot;
sz[pRoot]+=sz[qRoot];
}
}
@Override
public int getSize() {
return parent.length;
}
}
可以看出主要区别在于第43-48行代码，合并两棵树之前需要获取两棵树的节点个数，节点较少的树指向节点较大的树，并且需要更新新的树的节点个数。
第四个版本的并查集
在第二版本的基础上，使用 rank 优化，也就是在Union 操作时，深度较小的树指向节点数较大的树。之所以这样优化是假设一棵深度较大的树与一棵深度较小的树进行合并时，如果是大树指向小树，那么需要找到大树的根节点，而大树的根节点深度较高，操作起来更费时。为此，需要额外的一个 rank 数组，用来存储树的深度。
//第四版并查集, union过程基于rank优化, 矮树指向高树
//union O(n) O(h),h为树的高度
//isConnected(p,q) O(h),h为树的高度
public class UnionFind4 implements IUF{
private int[] parent;
private int[] rank;// rank[i]表示以i为根的树的高度
public UnionFind4(int size){
parent=new int[size];
rank=new int[size];
for (int i=0;i<size;i++){
parent[i]=i;
rank[i]=1;
}
}
//查询p的根节点,O(h)复杂度,h为树的高度
private int find(int p){
if (p<0 || p>=parent.length){
throw new IllegalArgumentException("Index is out of bound!");
}
while (p!=parent[p]){
p=parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if ( pRoot==qRoot ){
return;
}
if (rank[pRoot]<rank[qRoot]){
parent[pRoot]=qRoot;
}else if (rank[pRoot]>rank[qRoot]){
parent[qRoot]=pRoot;
} else {
parent[qRoot]=pRoot;
rank[pRoot]+=1;
}
}
@Override
public int getSize() {
return parent.length;
}
}
可以看出主要区别在于第43-50行代码，合并两棵树之前需要获取两棵树的深度，深度较小的树指向深圳较大的树，并且需要更新新的树的深度。具体的说是如果两棵树深度不一样，合并后的深度是原本深度较大的树的深度。若果两棵树深度相等，则合并后的深度是原本深度+1。
第五个版本的并查集
在第四版本的基础上，使用 路径压缩 优化，也就是在 Find 操作时，不断将遍历到的节点指向其父节点的父节点，以实现逐步降低树的深度。比如下图中的 find(4),一开始树的深度是5。随后节点4指向其父节点的父节点2，高度降低为4。再随后，节点2指向其父节点的父节点0，高度降低为3。
完整代码如下：
//第五版并查集, union过程基于rank优化+路径压缩优化
//union O(n) O(h),h为树的高度
//isConnected(p,q) O(h),h为树的高度
public class UnionFind5 implements IUF{
private int[] parent;
private int[] rank;// sz[i]表示以i为根的集合中元素个数
public UnionFind5(int size){
parent=new int[size];
rank=new int[size];
for (int i=0;i<size;i++){
parent[i]=i;
rank[i]=1;
}
}
//查询p的根节点,O(h)复杂度,h为树的高度
private int find(int p){
if (p<0 || p>=parent.length){
throw new IllegalArgumentException("Index is out of bound!");
}
while (p!=parent[p]){
parent[p]=parent[parent[p]];
p=parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p)==find(q);
}
@Override
public void unionElements(int p, int q) {
int pRoot=find(p);
int qRoot=find(q);
if ( pRoot==qRoot ){
return;
}
if (rank[pRoot]<rank[qRoot]){
parent[pRoot]=qRoot;
}else if (rank[pRoot]>rank[qRoot]){
parent[qRoot]=pRoot;
} else {
parent[qRoot]=pRoot;
rank[pRoot]+=1;
}
}
@Override
public int getSize() {
return parent.length;
}
}
可以看出主要区别在于第23-25行代码，在寻找根节点的过程中，不断地将当前节点指向父节点的父节点，直到到达根节点。
测试一下五个版本的并查集
先测试一下小规模的数据集，100000个元素，100000次Union 操作，100000次 Find 操作。
import java.util.Random;
public class Test {
private static double testUF(IUF uf, int m){
int size= uf.getSize();
Random random=new Random();
long startTime=System.nanoTime();
for (int i = 0; i < m; i++) {
int a= random.nextInt(size);
int b= random.nextInt(size);
uf.unionElements(a,b);
}
for (int i = 0; i < m; i++) {
int a= random.nextInt(size);
int b= random.nextInt(size);
uf.isConnected(a,b);
}
long endTime=System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
public static void main(String[] args) {
int size=100000;
int m=100000;
UnionFind1 uf1=new UnionFind1(size);
UnionFind2 uf2=new UnionFind2(size);
UnionFind3 uf3=new UnionFind3(size);
UnionFind4 uf4=new UnionFind4(size);
UnionFind5 uf5=new UnionFind5(size);
System.out.println("UnionFind 1 :"+testUF(uf1,m));
System.out.println("UnionFind 2 :"+testUF(uf2,m));
System.out.println("UnionFind 3 :"+testUF(uf3,m));
System.out.println("UnionFind 4 :"+testUF(uf4,m));
System.out.println("UnionFind 5 :"+testUF(uf5,m));
}
}
测试结果：
UnionFind 1 :6.8831883
UnionFind 2 :14.9014335
UnionFind 3 :0.0202739
UnionFind 4 :0.0136407
UnionFind 5 :0.0138095可以看出在较小数据规模时，第一个版本和第二个版本的并查集性能差距不大，仍然在一个数量级。但是第二三四个版本的并查集性能明显更优，而且三者性能差距也不大。
接下来使用更大数据规模来测试后三个版本的并查集，10000000个元素，10000000次Union 操作，10000000次 Find 操作。测试结果：
UnionFind 3 :5.3568896
UnionFind 4 :5.2921488
UnionFind 5 :4.2312699可以看出基于 rank 优化的性能要略微优于基于 size优化的，这是因为基于 rank 直接用深度来进行判别，比基于大小来判别更加合理，毕竟复杂度是和深度直接相关的，大的树不一定深度也大。基于路径压缩优化的效果则更加明显。
Last updated
Was this helpful?