欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 金融 > Java高阶数据结构-----并查集(详解)

Java高阶数据结构-----并查集(详解)

2024/11/30 14:38:00 来源:https://blog.csdn.net/2302_79862386/article/details/139607675  浏览:    关键词:Java高阶数据结构-----并查集(详解)

目录

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

🤪二.并查集代码:

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

A.省份数量

B.等式方程的可满足性


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

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

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

  2. (数组的值array[i]:) 数组中如果为负数,负号代表根,数字代表该集合中元素个数

  3. (数组的值array[i]:)数组中如果为非负数,代表该元素双亲在数组中的下标

并查集能干的事:

  1. 查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即:树中中元素为负数的位置)

  2. 查看两个元素是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根,如果根相同表明在同一个集合,否则不在

  3. 将两个集合归并成一个集合 将两个集合中的元素合并 将一个集合名称改成另一个集合的名称

🤪二.并查集代码:

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;}
}

运行结果:

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com