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
优秀博客
Java实现并查集_TheSevenSky的博客-CSDN博客_java并查集
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/223622.html原文链接：https://javaforall.net
