并查集（Union Find）

2022-04-05 176

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 并查集的介绍，包括并查集的两种实现方式、基于size的优化、基于rank的优化、路径压缩、路径分裂、路径减半

一、概述

并查集：一种树型数据结构，用于解决一些不相交集合的合并及查询问题。例如：有n个村庄，查询2个村庄之间是否有连接的路，连接2个村庄

两大核心：

查找 (Find) : 查找元素所在的集合

合并 (Union) : 将两个元素所在集合合并为一个集合

二、实现

并查集有两种常见的实现思路

快查（Quick Find）

查找（Find）的时间复杂度：O（1）
合并（Union）的时间复杂度：O（n）

快并（Quick Union）

查找（Find）的时间复杂度：O（logn）可以优化至O（a（n））a（n）< 5
合并（Union）的时间复杂度：O（logn）可以优化至O（a（n））a（n）< 5

使用数组实现树型结构，数组下标为元素，数组存储的值为父节点的值

创建抽象类Union Find

publicabstractclassUnionFind {
int[] parents;
/*** 初始化并查集* @param capacity*/publicUnionFind(intcapacity){
if(capacity<0) {
thrownewIllegalArgumentException("capacity must be >=0");
        }
//初始时每一个元素父节点（根结点）是自己parents=newint[capacity];
for(inti=0; i<parents.length;i++) {
parents[i] =i;
        }
    }
/***  检查v1 v2 是否属于同一个集合*/publicbooleanisSame(intv1,intv2) {
returnfind(v1) ==find(v2);
    }
/***  查找v所属的集合 （根节点）*/publicabstractintfind(intv);
/***  合并v1 v2 所属的集合*/publicabstractvoidunion(intv1, intv2);
// 范围检查publicvoidrangeCheck(intv)  {
if(v<0||v>parents.length)
thrownewIllegalArgumentException("v is out of capacity");
    }
}

2.1 Quick Find实现

以Quick Find实现的并查集，树的高度最高为2，每个节点的父节点就是根节点

publicclassUnionFind_QFextendsUnionFind {
publicUnionFind_QF(intcapacity) {
super(capacity);
    }
// 查@Overridepublicintfind(intv) {
rangeCheck(v);
returnparents[v];
    }
// 并 将v1所在集合并到v2所在集合上@Overridepublicvoidunion(intv1, intv2) {
// 查找v1 v2 的父（根）节点intp1=find(v1);
intp2=find(v2);
if(p1==p2) return;
//将所有以v1的根节点为根节点的元素全部并到v2所在集合上 即父节点改为v2的父节点for(inti=0; i<parents.length; i++) {
if(parents[i] ==p1) {
parents[i] =p2;
        }
    }
  }
}

2.2 Quick Union实现

publicclassUnionFind_QUextendsUnionFind {
publicUnionFind_QU(intcapacity) {
super(capacity);
    }
//查某一个元素的根节点@Overridepublicintfind(intv) {
//检查下标是否越界rangeCheck(v);
// 一直循环查找节点的根节点while (v!=parents[v]) {
v=parents[v];
        }
returnv;
    }
//V1 并到 v2 中@Overridepublicvoidunion(intv1, intv2) {
intp1=find(v1);
intp2=find(v2);
if(p1==p2) return;
//将v1 根节点 的 父节点 修改为 v2的根结点 完成合并parents[p1] =p2;
    }
}

三、优化

并查集常用快并来实现，但是快并有时会出现树不平衡的情况

有两种优化思路：rank优化，size优化

3.1基于size的优化

核心思想：元素少的树嫁接到元素多的树

publicclassUniondFind_QU_SextendsUnionFind{
// 创建sizes 数组记录 以元素（下标）为根结点的元素（节点）个数privateint[] sizes;
publicUniondFind_QU_S(intcapacity) {
super(capacity);
sizes=newint[capacity];
//初始都为 1for(inti=0;i<sizes.length;i++) {
sizes[i] =1;
            }
    }
@Overridepublicintfind(intv) {
rangeCheck(v);
while (v!=parents[v]) {
v=parents[v];
        }
returnv;
    }
@Overridepublicvoidunion(intv1, intv2) {
intp1=find(v1);
intp2=find(v2);
if(p1==p2) return;
//如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上，并且更新p2为根结点的元素个数if(sizes[p1] <sizes[p2]) {
parents[p1] =p2;
sizes[p2] +=sizes[p1];
// 反之 则p2 并到 p1 上，更新p1为根结点的元素个数    }else {
parents[p2] =p1;
sizes[p1] +=sizes[p2];
        }
    }
}

基于size优化还有可能会导致树不平衡

3.2基于rank优化

核心思想：矮的树嫁接到高的树

publicclassUnionFind_QU_RextendsUnionFind_QU {
// 创建rank数组  ranks[i] 代表以i为根节点的树的高度privateint[] ranks;
publicUnionFind_QU_R(intcapacity) {
super(capacity);
ranks=newint[capacity];
for(inti=0;i<ranks.length;i++) {
ranks[i] =1;
        }
    }
publicvoidunion(intv1, intv2) {
intp1=find(v1);
intp2=find(v2);
if(p1==p2) return;
// p1 并到 p2 上 p2为根 树的高度不变if(ranks[p1] <ranks[p2]) {
parents[p1] =p2;
// p2 并到 p1 上 p1为根 树的高度不变        } elseif(ranks[p1] >ranks[p2]) {
parents[p2] =p1;
        }else {
// 高度相同 p1 并到 p2上，p2为根 树的高度+1parents[p1] =p2;
ranks[p2] +=1;
        }
    }
}

基于rank优化，随着Union次数的增多，树的高度依然会越来越高导致find操作变慢

有三种思路可以继续优化：路径压缩、路径分裂、路径减半

3.2.1路径压缩（Path Compression ）

在find时使路径上的所有节点都指向根节点，从而降低树的高度

/***  Quick Union -基于rank的优化  -路径压缩**/publicclassUnionFind_QU_R_PCextendsUnionFind_QU_R {
publicUnionFind_QU_R_PC(intcapacity) {
super(capacity);
    }
@Overridepublicintfind(intv) {
rangeCheck(v);
if(parents[v] !=v) {
//递归 使得从当前v 到根节点 之间的 所有节点的 父节点都改为根节点parents[v] =find(parents[v]);
        }
returnparents[v];
    }
}

虽然能降低树的高度，但是实现成本稍高

3.2.2路径分裂（Path Spliting）

使路径上的每个节点都指向其祖父节点

/***  Quick Union -基于rank的优化  -路径分裂**/publicclassUnionFind_QU_R_PSextendsUnionFind_QU_R {
publicUnionFind_QU_R_PS(intcapacity) {
super(capacity);
    }
@Overridepublicintfind(intv) {
rangeCheck(v);
while(v!=parents[v]) {
intp=parents[v];
parents[v] =parents[parents[v]];
v=p;
        }
returnv;
    }
}

3.2.3路径减半（Path Halving）

使路径上每隔一个节点就指向其祖父节点

/***  Quick Union -基于rank的优化  -路径减半**/publicclassUnionFind_QU_R_PHextendsUnionFind_QU_R {
publicUnionFind_QU_R_PH(intcapacity) {
super(capacity);
    }
publicintfind(intv) {
rangeCheck(v);
while(v!=parents[v]) {
parents[v] =parents[parents[v]];
v=parents[v];
        }
returnv;
    }    
 }

使用Quick Union + 基于rank的优化 + 路径分裂或路径减半

可以保证每个操作的均摊时间复杂度为O(a(n)) , a(n) < 5

文章标签：

存储