1、并查集定义
并查集是一种数据结构，常用来描述集合。 在一些应用的问题中，需将n个不同的元素划分成一组不相交的集合。开始时，每个元素自成一格单元素集合，然后按一定顺序将属于同一组的元素的集合合并。其间要反复用到查询某个元素属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。
2、并查集可以解决的常规问题
（1）某个元素是否属于某个集合；
（2）某两个节点是否属于同一个集合（亲戚关系判断）
（3）判断图是否有环问题
3、并查集的分类
（1）Union-find 简单并查集
（2）Quick-union 优化的并查集
（3）加权值 quick-union(处理了方法2最坏的情况)
（4）路径压缩加权值quick-union
4、常见问题描述和并查集关键函数
常见的问题是给一堆节点之间的连接关系，要我们来判断这些节点可以划分为几个集合，或者给一堆图的节点与边的关系，问我们这个图是否有环等问题。
为了解决类如上述问题，我们采用并查集需要定义两个关键函数：
（1）find(x) :找出元素x所有集合（帮派）的老大；
（2）union(x,y):将元素x和元素y所在的两个集合合并为一个新的集合（小帮派合并为大帮派）
5、并查集的实现
5.1、并查集构建的思想
用比较通俗易懂的话来说，并查集就是一个建立帮派的过程，
1）刚开始，每一个元素各成一派，
2）然后根据给点条件的约束，存在约束的两个节点（只要存在约束，那么这两个点就要划分到同一个集合），若此时这连个节点分属于不同的集合，那么先找到各自帮派的老大，
3）然后 其中一个帮派的老大 认另一个帮派的老大 做大哥，那么这两个帮派就合并了，也就满足了有约束关系的两个节点应该划分到同一个集合（帮派），
4）以此类推，直到遍历完所有给定的约束，那么此时的帮派建立也就结束了。
5）最后，我们就可以统计总的有多少个帮派，派生问题还有判断图是不是有环、每个帮派有多少人头等子问题。
5.2、构建并查集中需考虑的几个点
1）在构建过程中，我们需要记录每个节点的老大是谁，所以涉及到初始化的问题，我们构建一个parent【i】数组，数组中存储的值表示元素 i 的老大(父亲)，刚开始的时候，因为每个元素各自为王，所以初始化parent【i】= -1;
2)随着构建给定的节点约束关系，不断合并集合，每一个节点的parent【i】可能被更新为其他节点，所以当并查集构建结束后，我们统计parent数组中，还有几个“-1”,那么就说明还剩下几个超级老大，对应几个帮派集合（因为刚开始 每个"-1"对应一个集合帮派，并查集构建结束，parent【i】不是“-1”的说明被合并了，，剩下"-1"的个数就是 合并后还有几个集合帮派。）
3）判断派生问题，图是否存在环，假如当前两个节点存在边连接，根据并查集的定义，我们需要把这两个节点划分到同一个集合，所以我们先别分找这两个节点所属的各自帮派老大 [find(x)函函数功能] 如果找到这两个节点的帮派老大是同一个人，说明这两个节点本身就属于同一个集合了，两个节点可以相互联通，，，现在两节点又存在一条边直接连接，，那不就构成 环 了。
5.3、具体代码实现
如上文所述，核心的两个函数，一个是找当前节点所述帮派老大find_root(x)；
一个核心函数是 合并两个集合帮派 union(int x,int y)
public static class MyUnion {
private int[] parent; //记录每一个节点的父节点
private final int[] sum;//记录每一个集合（帮派）的成员数目，初始化的时候因为每个节点自成一派，所以初始每个帮派数目都是1
public int size;//记录总的有多少个集合(帮派)
//初始化
//刚开始，假设每个数据是一个分组，然后根据遍历关系，不断修改不同数据之间的连接
//parent[i] 表示元素i的根节点(父亲)为parent[i]
//当遍历完所有的关系后，我们统计 parent数组中还有几个-1，那就说明这些关系有几个分组
//假设当前关系约束的两个节点，我们要先找到两个节点的根节点，判断根节点是否相同
//说明两个节点属于同一个集合 并且已经成环
//若两个节点的根节点不同，然后把一个集合的帮派合并到另一个集合中
// 1、初始化，每个节点各成一派，根节点否设置为-1
public MyUnion(int length){
this.parent = new int[length];
this.size = length;
this.sum = new int[length];
for(int i=0;i<length;i++){
parent[i]=-1;
sum[i]=1;
}
}
//2、 找某个节点的所属集合(帮派)的老大
public int find_root(int i){
if(parent[i]==-1){
//说明自己根节点为-1，自己就是帮派老大
return i;
}else {
//比如当前节点i的老大存的是2，那么我们在递归去找2的老大，如果此时2的老大是 -1，说明i
//所述的帮派 老大就是 节点2了
return find_root(parent[i]);//递归调用，只有parent[i]==-1,此时的i才是某个集合帮派的老大
}
}
//3、合并 两个帮派(集合)
public void union_fun(int i,int j){
//先找到各自节点的帮派老大
int root_i = find_root(i);
int root_j =find_root(j);
if(root_i !=root_j){
//两个帮派老大不一样的时候才需要合并
parent[root_i]=root_j; //这里相当于i所在的帮派合并到j的帮派
sum[root_j] +=sum[root_i];//那么 i帮派人数都要算到j的帮派中去
size--;//每合并了两个帮派，总的帮派数目减少1
}
}
// 4、查询某两个节点 是否属于同一个集合(帮派)
//即验证这两个节点的 老大(根)是否相同，相同就说明是一个帮派
// 如果两个节点有连接，，此时又发现两个节点处于同一个集合（都是同一个老大），那么对应图 必然成环
public boolean isconnected(int i,int j){
int root_i = find_root(i);
int root_j =find_root(j);
return root_i == root_j; //true or false
}
}
优秀博客
Java实现并查集_TheSevenSky的博客-CSDN博客_java并查集
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
