当前位置：首页 > news >正文

Java高阶数据结构-----并查集（详解）

news 来源：原创 2024/9/29 8:20:39

🧐一.并查集的基本概念&实例：

🤪二.并查集代码：

😂三：并查集的一些习题：

A.省份数量

B.等式方程的可满足性

🧐一.并查集的基本概念&实例：

并查集概念：将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-ﬁnd set)。

有了上面的一定了解，我们再来看一个实例：

比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。(负号下文解释)

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。

在公司工作一段时间后，西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：

现在0集合有7个人，2集合有3个人，总共两个朋友圈,负数的个数就是集合的个数

注意事项：

我们一般将数组中的元素初始化为-1

(数组的下标:) 数组的下标对应集合中元素的编号

（数组的值array[i]:） 数组中如果为负数，负号代表根，数字代表该集合中元素个数

（数组的值array[i]:）数组中如果为非负数，代表该元素双亲在数组中的下标

并查集能干的事：

查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
查看两个元素是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
将两个集合归并成一个集合 将两个集合中的元素合并将一个集合名称改成另一个集合的名称

🤪二.并查集代码：

import java.util.*;
public class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem = new int[n];Arrays.fill(elem,-1);}//查询x的根节点，返回根节点的下标public int findRoot(int x){if(x < 0){throw new IndexOutOfBoundsException("下标不合法，是负数");}//一直等到数组里面的值为负数时，才找到一个根while(elem[x] >= 0){x = elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return ;}elem[index1] = elem[index1] + elem[index2];elem[index2] = index1;}//查询集合的个数public int getCount(){int count = 0;for(int x : elem){if(x < 0) count++;}return count;}
}

那我们趁热打铁，来做两道题练习一下：

😂三：并查集的一些习题：

A.省份数量
题目链接：. - 力扣（LeetCode）

思路：我们初始化一个一维数组表示并查集（数组大小为城市的个数），遍历这个二维数组（isConnected[i][j] 表示 i , j 两个城市相连），用并查集将相连接的城市合并到一个集合中，最后统计集合中元素的个数，就是要求的省份个数

class Solution {//A.省份数量public int findCircleNum(int[][] isConnected) {int n = isConnected.length;UnionFindSet ufs = new UnionFindSet(n);//将连接在一起的城市合并for(int i = 0;i < isConnected.length;i++){for(int j = 0;j < isConnected[0].length;j++){if(isConnected[i][j] == 1){ufs.union(i,j);}}}//查找连接在一起的城市，即省份的个数，直接返回return ufs.getCount();}
}
/* 并查集的实现*/
class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem = new int[n];Arrays.fill(elem,-1);}//查询x的根节点，返回根节点的下标public int findRoot(int x){if(x < 0){throw new IndexOutOfBoundsException("下标不合法，是负数");}while(elem[x] >= 0){x = elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return ;}elem[index1] = elem[index1] + elem[index2];elem[index2] = index1;}//查询集合的个数public int getCount(){int count = 0;for(int x : elem){if(x < 0) count++;}return count;}}

运行结果：

B.等式方程的可满足性
题目链接：. - 力扣（LeetCode）

思路：我们将具有相同属性的元素放入一个集合中，接着再遍历一遍字符串数组，如果字符串中对应的元素是！说明不是一个集合，再从上述并查集中查找，如果是一个集合的(矛盾了)，返回false;遍历完成后也没有出现上述情况，说明都是一个集合里，返回true，那么这个等式方程组就满足条件

class Solution {//B.等式方程的可满足性public boolean equationsPossible(String[] equations) {UnionFindSet ufs = new UnionFindSet(26);//将具有相同属性的元素放入一个集合中for(int i = 0;i < equations.length;i++){if(equations[i].charAt(1) == '='){ufs.union(equations[i].charAt(0) - 'a',equations[i].charAt(3) - 'a');}}//如果字符串中对应的元素是！，说明不是一个集合，再从上述并查集中查找， (矛盾了)如果是一个集合的，返回false;for(int i  = 0;i < equations.length;i++){if(equations[i].charAt(1) == '!'){//查找根节点的下标位置int index1 = ufs.findRoot(equations[i].charAt(0) - 'a');int index2 = ufs.findRoot(equations[i].charAt(3) - 'a');if(index1 == index2) return false;}}return true;}
}
/* 并查集的实现 */
class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem = new int[n];Arrays.fill(elem,-1);}//查询x的根节点，返回根节点的下标public int findRoot(int x){if(x < 0){throw new IndexOutOfBoundsException("下标不合法，是负数");}while(elem[x] >= 0){x = elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 = findRoot(x1);int index2 = findRoot(x2);if(index1 == index2){return ;}elem[index1] = elem[index1] + elem[index2];elem[index2] = index1;}//查询集合的个数public int getCount(){int count = 0;for(int x : elem){if(x < 0) count++;}return count;}
}

运行结果：

结语： 写博客不仅仅是为了分享学习经历，同时这也有利于我巩固知识点，总结该知识点，由于作者水平有限，对文章有任何问题的还请指出，接受大家的批评，让我改进。同时也希望读者们不吝啬你们的点赞+收藏+关注，你们的鼓励是我创作的最大动力！