当前位置:   article > 正文

并查集(不相交集)详解

并查集

目录

一.并查集

1.什么是并查集

2.并查集的基本操作

3.并查集的应用

4.力扣上的题目

二.三大操作

1.初始化

2.查找

 3.合并

三.省份数量

1.题目描述

2.问题分析

3.代码实现

四.冗余连接

1.题目描述

2.问题分析

3.代码实现


一.并查集

1.什么是并查集

并查集(Disjoint-set Union 或 Union-find)是一种数据结构,用于维护一些不相交(disjoint)的集合,支持合并两个集合以及判断两个元素是否属于同一个集合。

并查集可以使用树来实现,每个集合可以看做是一棵树,代表元素是根节点。使用路径压缩可以减少查找操作的时间复杂度,使用按秩合并可以减少合并操作的时间复杂度,使得并查集的时间复杂度可以达到近乎常数级别,因此在一些算法中广泛应用,比如 Kruskal 算法和 Tarjan 算法。

2.并查集的基本操作

  1. 初始化:将每个元素初始化为单独的集合,每个集合的代表元素就是自己;
  2. 查找:给定一个元素,找到它所属的集合的代表元素;
  3. 合并:将两个集合合并成一个集合,即将其中一个集合的代表元素作为另一个集合的代表元素的子节点。

3.并查集的应用

并查集是一种用于维护集合(组)的数据结构,它通常用于解决一些离线查询、动态连通性和图论等相关问题。

其中最常见的应用场景是解决图论中的连通性问题,例如判断图中两个节点是否连通、查找图的连通分量、判断图是否为一棵树等等。并查集可以快速地合并两个节点所在的集合,以及查询两个节点是否属于同一个集合,从而有效地判断图的连通性。

并查集还可以用于解决一些离线查询问题,例如静态连通性查询和最小生成树问题,以及一些动态连通性问题,例如支持动态加边和删边的连通性问题。

总之,如果需要维护集合(组)的连通性信息,就可以考虑使用并查集。

现在举一个现实中的问题,判断一个人是否属于一个家族,通常一个家族里面两个人可能不是彼此认识的,但是A和B是亲属关系,B和C是亲属关系,此时我们可以判断出A和C就是亲属关系

 由于家族关系可能错综复杂,这个时候我们是否可以找一个代表,这个人来代表这个家族,比如选择A来代表家族A,D来代表家族B,那么只要你和A有关系,你就是属于A家族的,你和D有关系,你就是属于B家族的

并查集就是解决这样的问题的.

4.力扣上的题目

以下是一些力扣(LeetCode)上关于并查集(Union Find)的题目:

  1. 朋友圈(547) https://leetcode-cn.com/problems/friend-circles/

  2. 冗余连接(684) https://leetcode-cn.com/problems/redundant-connection/

  3. 冗余连接 II(685) https://leetcode-cn.com/problems/redundant-connection-ii/

  4. 岛屿数量(200) https://leetcode-cn.com/problems/number-of-islands/

  5. 连通网络的操作次数(1319) https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/

  6. 表示数值的字符串(剑指 Offer 20) https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/

  7. 最大连通面积(面试题 16.19) https://leetcode-cn.com/problems/pond-sizes-lcci/

  8. 能否连接形成区域(面试题 16.19) https://leetcode-cn.com/problems/pond-sizes-lcci/

  9. 合并账户(721) https://leetcode-cn.com/problems/accounts-merge/

  10. 判断能否形成等差数列(1502) https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence/

以上是一些力扣上的并查集题目,建议在练习时,先自己尝试思考解法,如果卡在某个地方,可以查看题解或者向其他程序员求助。

二.三大操作

1.初始化

我们把数组初始化-1,具体的作用我们之后再来分析具体的用处,具体含义就是,这个负数的相反数为这棵树的高度-1

  1. public void init(int[] parent) {
  2. //初始值设置为-1
  3. for (int i = 0; i < parent.length; ++i) {
  4. parent[i] = -1;
  5. }
  6. }

2.查找

不进行路径压缩的查找简单粗暴的,它的目的就是为了找到结点i的根结点,直接看代码

  1. public int find(int[] parent, int i) {
  2. if (parent[i] < 0) {//当前结点为根结点,终止
  3. return i;
  4. } else {
  5. return parent[i]; //返回父节点
  6. }
  7. }

这个时候我们来研究一下进行路径压缩的查找方式,我们需要合并0和4,如果我们只是粗暴的合并的话,这个时候0指向3,这个时候其实的查询长度就是越来越长,时间复杂度为O(n)

 所以这个时候我们不进行路径压缩,压缩之后的图是这样的,这个时候时间复杂度大大降低,我们每次查找根结点的时候,只需要查找一次(递归一次)便可以找到根结点

进行路径压缩的查找方法要进行两个操作,最终目的肯定还是要找寻到根结点,但是其次他也进行了路径的压缩,例如下图一样,把本来的4指向3,修改成了4指向了2,其实可以精炼成一句话:找到根结点,并且把路径上所有节点的父亲结点修改为根结点.这样树的高度就变成了1(只含有一个结点(根结点)的高度为0).

  1. public int find(int[] parent, int i) {
  2. if (parent[i] < 0) {//当前结点为根结点,终止
  3. return i;
  4. } else {
  5. parent[i] = find(parent, parent[i]); //父节点设为根结点
  6. return parent[i]; //返回父节点
  7. }
  8. }

 3.合并

合并操作也可以简单粗暴的进行合成,我们只需要找到各自的祖先,任意的将一个合并到另一个上边即可,直接看代码

  1. public void union(int[] parent, int i, int j) {
  2. int i_parent = find(parent, i);//寻找i的根结点
  3. int j_parent = find(parent, j);//寻找j的根结点
  4. parent[i_parent]=j_parent;//将根结点为i_parent的树合并到根结点j_parent上
  5. }

如果我们这个时候进行合并可能会出现这种情况,也就是一个高度较大的数合并到了一个高度较小的树上面,这个时候树的高度就会增加,如果我们是高度小的树合并到高度较大的树上边(两颗树的高度不相等),这个时候树的高度便不会增加,自然查找的时候会更加快速的查找到.

进行按秩(树的高度)进行合并

这种合并方式就是为了解决上面所提到的问题,合并是便会是这种情况,但是我们如果判断两棵树的高度大小呢,这个时候就可以解释以下初始化的为-1的目的了,一:如果当前结点的值为负数,可以判断当前结点为根结点,二.当前结点越小(也就是相反数越大),说明当前树的高度越大,我们只需要把更大的根结点的值合并到更小的根结点值上,便可以解决这个问题了.

这个时候存在一个特殊情况,也就是两棵树的高度一样高.这个时候无论如何进行合并,树的高度度会增加,因此这个时候我们可以把一个根结点合并到另一个根结点上,并把合并到的根结点的值减一

  1. public void union(int[] parent, int i, int j) {
  2. int i_parent = find(parent, i);//寻找i的根结点
  3. int j_parent = find(parent, j);//寻找j的根结点
  4. if (i_parent != j_parent) {//此时的根结点相同,没有合并的必要
  5. if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
  6. parent[j_parent] = i_parent;//把j_parent合并到i_parent上
  7. } else {
  8. if (parent[i_parent] == parent[j_parent]) {
  9. parent[j_parent]--;
  10. }
  11. parent[i_parent] = j_parent;//把i_parent合并到j_parent上
  12. }
  13. }
  14. }

三.省份数量

1.题目描述

n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

力扣:力扣

2.问题分析

这是一道很典型的并查集问题,题目的意思就是城市之间相连就是一个省份,把相连的城市合并为一颗树,最终就是寻找有多少个根结点(有多少颗树),也就是parent[i]有多少个是小于0的值,就是一棵树,最终返回数量就可以了

3.代码实现

  1. public void init(int[] parent) {
  2. //初始值设置为-1
  3. for (int i = 0; i < parent.length; ++i) {
  4. parent[i] = -1;
  5. }
  6. }
  7. public int find(int[] parent, int i) {
  8. if (parent[i]<0) {
  9. return i;
  10. } else {
  11. parent[i] = find(parent, parent[i]); //父节点设为根结点
  12. return parent[i]; //返回父节点
  13. }
  14. }
  15. public void union(int[] parent, int i, int j) {
  16. int i_parent = find(parent, i);//寻找i的祖先
  17. int j_parent = find(parent, j);//寻找j的祖先
  18. if (i_parent != j_parent) {//此时的祖先相同,没有合并的必要
  19. if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
  20. parent[j_parent] = i_parent;//把j_parent合并到i_parent上
  21. } else {
  22. if (parent[i_parent] == parent[j_parent]) {
  23. parent[j_parent]--;
  24. }
  25. parent[i_parent] = j_parent;//把i_parent合并到j_parent上
  26. }
  27. }
  28. }
  29. public int findCircleNum(int[][] isConnected) {
  30. int[] parent = new int[isConnected.length];
  31. init(parent);
  32. for (int i = 0; i < isConnected.length; ++i) {
  33. for (int j = i + 1; j < isConnected[0].length; ++j) {
  34. if (isConnected[i][j] == 1) {
  35. union(parent, i, j);
  36. }
  37. }
  38. }
  39. int cnt = 0;
  40. for (int i = 0; i < parent.length; ++i) {
  41. if (parent[i] < 0)
  42. cnt++;
  43. }
  44. return cnt;
  45. }

四.冗余连接

1.题目描述

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 aibi 之间存在一条边。

请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的边。

力扣:力扣

2.问题分析

题目的意思就是不能出现环,也就是如果两个两个点已经连通了,这个时候不能再在这两个点添加一条边,这个时候就冗余了,我们都知道一个连通分量有n个顶点,n-1条边,而这道题一共有n条边,我们需要寻找的就是这一条冗余的边,当find(parent,i,j)的根结点一样的时候,这个时候这两个顶点之间的边一定是冗余的,找到这样的一条边即可.

3.代码实现

  1. public void init(int[] parent) {
  2. for (int i = 0; i < parent.length; ++i) {
  3. parent[i] = -1;
  4. }
  5. }
  6. public int find(int[] parent, int i) {
  7. if (parent[i] < 0)
  8. return i;
  9. else {
  10. parent[i] = find(parent, parent[i]);
  11. return parent[i];
  12. }
  13. }
  14. public void union(int[] parent, int i, int j) {
  15. int i_parent = find(parent, i);
  16. int j_parent = find(parent, j);
  17. if (i_parent != j_parent) {
  18. if (parent[i_parent] < parent[j_parent]) {
  19. parent[j_parent] = i_parent;
  20. } else {
  21. if (parent[i_parent] == parent[j_parent]) {
  22. parent[j_parent]--;
  23. }
  24. parent[i_parent] = j_parent;
  25. }
  26. }
  27. }
  28. public int[] findRedundantConnection(int[][] edges) {
  29. int[] parent = new int[edges.length+1];
  30. init(parent);
  31. for (int i = 0; i < edges.length; ++i) {
  32. if (find(parent, edges[i][0]) != find(parent, edges[i][1])) {
  33. union(parent, edges[i][0], edges[i][1]);
  34. } else {
  35. return edges[i];
  36. }
  37. }
  38. return null;
  39. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/792322
推荐阅读
相关标签
  

闽ICP备14008679号