并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。本文将通过java实现并查集，感兴趣的小伙伴可以了解一下

一、概述

联合集合(Union collection):一种树状数据结构，用于解决一些不相交集合的合并和查询问题。例如，如果有n个村庄，检查两个村庄之间是否有连接道路来连接两个村庄。

两个内核:

查找:查找元素所在的集合。

Union:将两个元素的集合合并成一个集合。

二、实现

实现并行采集有两种常见的方式。

查找(快速查找)

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

快速接头

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

用数组实现树形结构。数组的下标是元素，数组中存储的值是父节点的值。

创建抽象类Union Find

public abstract class UnionFind { int[] parents;/** * 初始化并查集 * @param capacity */public UnionFind(int capacity){if(capacity lt; 0) {throw new IllegalArgumentException("capacity must be gt;=0");} //初始时每一个元素父节点（根结点）是自己parents = new int[capacity];for(int i = 0; i lt; parents.length;i++) {parents[i] = i;}} /** * 检查v1 v2 是否属于同一个集合 */public boolean isSame(int v1,int v2) {return find(v1) == find(v2);} /** * 查找v所属的集合 （根节点） */public abstract int find(int v); /** * 合并v1 v2 所属的集合 */public abstract void union(int v1, int v2);// 范围检查public void rangeCheck(int v) {if(vlt;0 || v gt; parents.length)throw new IllegalArgumentException("v is out of capacity");}}

2.1 Quick Find实现

快速查找实现的并集中树的最高高度为2，每个节点的父节点为根节点。

public class UnionFind_QF extends UnionFind {public UnionFind_QF(int capacity) {super(capacity);} // 查@Overridepublic int find(int v) {rangeCheck(v);return parents[v];} // 并 将v1所在集合并到v2所在集合上@Overridepublic void union(int v1, int v2) { // 查找v1 v2 的父（根）节点int p1= find(v1);int p2 = find(v2);if(p1 == p2) return; //将所有以v1的根节点为根节点的元素全部并到v2所在集合上 即父节点改为v2的父节点for(int i = 0; ilt; parents.length; i++) {if(parents[i] == p1) {parents[i] = p2;}} }}

2.2 Quick Union实现

public class UnionFind_QU extends UnionFind { public UnionFind_QU(int capacity) {super(capacity);} //查某一个元素的根节点@Overridepublic int find(int v) { //检查下标是否越界rangeCheck(v); // 一直循环查找节点的根节点while (v != parents[v]) {v = parents[v];}return v;} //V1 并到 v2 中@Overridepublic void union(int v1, int v2) {int p1 = find(v1);int p2 = find(v2);if(p1 == p2) return; //将v1 根节点 的 父节点 修改为 v2的根结点 完成合并parents[p1] = p2;}}

三、优化

联合检查通常通过快速联合来实现，但有时树是不平衡的。

优化思路有两种:秩优化和大小优化？

3.1基于size的优化

核心思想:元素少的树嫁接到元素多的树上。

public class UniondFind_QU_S extends UnionFind{ // 创建sizes 数组记录 以元素（下标）为根结点的元素（节点）个数private int[] sizes; public UniondFind_QU_S(int capacity) {super(capacity); sizes = new int[capacity]; //初始都为 1for(int i = 0;i lt; sizes.length;i++) {sizes[i] = 1;}} @Overridepublic int find(int v) { rangeCheck(v); while (v != parents[v]) {v = parents[v];}return v;} @Overridepublic void union(int v1, int v2) {int p1 = find(v1);int p2 = find(v2);if(p1 == p2) return; //如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上，并且更新p2为根结点的元素个数if(sizes[p1] lt; sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; // 反之 则p2 并到 p1 上，更新p1为根结点的元素个数}else {parents[p2] = p1;sizes[p1] += sizes[p2];}}}

基于大小的优化也可能导致树不平衡。

3.2基于rank优化

核心思想:一棵矮树嫁接到一棵大树上。

public class UnionFind_QU_R extends UnionFind_QU { // 创建rank数组 ranks[i] 代表以i为根节点的树的高度 private int[] ranks; public UnionFind_QU_R(int capacity) {super(capacity); ranks = new int[capacity]; for(int i = 0;i lt; 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; // p1 并到 p2 上 p2为根 树的高度不变if(ranks[p1] lt; ranks[p2]) {parents[p1] = p2; // p2 并到 p1 上 p1为根 树的高度不变} else if(ranks[p1] gt; ranks[p2]) {parents[p2] = p1; }else { // 高度相同 p1 并到 p2上，p2为根 树的高度+1parents[p1] = p2;ranks[p2] += 1;}}}

基于秩优化，随着联合次数的增加，树的高度还是会越来越高？导致查找操作变慢。

继续优化有三种方式:路径压缩、路径分裂和路径减半。

3.2.1路径压缩（Path Compression ）

查找时，路径上的所有节点都指向根节点，从而降低树的高度。

/** * Quick Union -基于rank的优化 -路径压缩 * */public class UnionFind_QU_R_PC extends UnionFind_QU_R { public UnionFind_QU_R_PC(int capacity) {super(capacity);} @Overridepublic int find(int v) {rangeCheck(v); if(parents[v] != v) { //递归 使得从当前v 到根节点 之间的 所有节点的 父节点都改为根节点parents[v] = find(parents[v]);}return parents[v];}}

虽然可以降低树的高度，但是实现成本略高？

3.2.2路径分裂（Path Spliting）

使路径上的每个节点指向它的祖父节点。

/** * Quick Union -基于rank的优化 -路径分裂 * */public class UnionFind_QU_R_PS extends UnionFind_QU_R { public UnionFind_QU_R_PS(int capacity) {super(capacity);} @Overridepublic int find(int v) {rangeCheck(v);while(v != parents[v]) { int p = parents[v];parents[v] = parents[parents[v]];v = p;}return v;}}

3.2.3路径减半（Path Halving）

使路径上的每隔一个节点指向它的祖父节点。

/** * Quick Union -基于rank的优化 -路径减半 * */public class UnionFind_QU_R_PH extends UnionFind_QU_R { public UnionFind_QU_R_PH(int capacity) {super(capacity);} public int find(int v) { rangeCheck(v); while(v != parents[v]) {parents[v] = parents[parents[v]];v = parents[v];}return v;} }

使用快速联合+基于排名的优化+路径分割或路径减半。

它能保证每次操作的平均时间复杂度为O(a(n))，a(n)lt；五

关于java数据结构和搜索集合的详细解释，本文到此结束。有关java搜索集合的更多信息，请搜索源搜索网之前的文章或继续浏览下面的相关文章。希望大家以后