devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】--并查集

作者：weixin_40725706 | 2024-07-16 20:26:38

赞

踩

并查集

目录

一、概念

​编辑

二、应用场景--“连接”问题（属于同一Qu

三、实现思路

 四、如何存储数据

五、定义接口

1.初始化（init）

2.其他

isSame（）

六、抽象类

六、Quick Find【v1 所在集合的所有元素都指向 v2 的根节点】

1.Union

1.Union图解

2.注意点： 

3.代码实现

2.find 

1.find图解

2.代码实现

3.完整代码

七、（常用）Quick Union【v1 的根节点指向 v2 的根节点】

1.Union

1.注意点

2.Quick Union图解

3.代码实现

2.find

代码实现

3.完整代码

八、Quick Union的优化

1.简介

 2.方案一：基于size的优化【元素少的树 嫁接到 元素多的树】

​编辑 

3.方案二：基于rank的优化【矮的树 嫁接到 高的树】

九、路径压缩（Path Compression）

1.什么是路径压缩？

2.代码实现

十、路径分裂（Path Spliting）

1.概念

 2.代码实现

十一、路径减半（Path Halving）

1.概念

2.代码实现

十二、总结

一、概念

并查集(Disjoint Set)是一种可以动态维护若干个不重叠的集合，并支持合并与查询两种操作的一种数据结构。按照一般的思路，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中，这样时间复杂度就太高啦。而并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。

并查集支持查找一个元素所属的集合以及两个元素各自所属的集合的合并等运算,当给出两个元素的一个无序对(a,b)时,需要快速“合并” a 和 b 分别所在的集合,这期间需要反复“查找”某元素所在的集合。“并”、“查”和“集” 3 个字由此而来。在这种数据类型中,n个不同的元素被分为若干组。每组是一个集合,这种集合叫分离集合,称之为并查集。

二、应用场景--“连接”问题（属于同一Qu

并查集是一种非常精巧而实用的数据结构，它注意用于处理一些不相交集合的合并温问题。一些常见的用途有连通子图，求最小生成树Kruskal算法和求最近公共祖先（LCA）。

三、实现思路

 四、如何存储数据

假设并查集处理的数据都是整型，那么可以用整型数组来存储数据。

  • 数组索引代表元素值
  • 索引对应的值代表这个元素的根节点

并查集是可以用数组实现的树形结构（二叉堆、优先级队列也是可以用数组实现的树形结构） 

五、定义接口

1.初始化（init）

初始化时，每个元素各自属于一个单元素集合

  1. private int[] parents;
  2. public UnionFind(int capacity){
  3. 	if(capacity < 0){
  4. 		throw new IllegalArgumentException("capacity must >= 1");
  5. 	}
  6. 	parents = new int[capacity];
  7. 	for (int i = 0; i < parents.length; i++) {
  8. 		parents[i] = i;
  9. 	}
  10. }

2.其他

  1. /**
  2.  * 查找v所属的集合(根结点)
  3.  */
  4. public abstract int find(int v);
  5. /**
  6.  * 合并v1、v2所在的集合
  7.  */
  8. public abstract void union(int v1, int v2);
  9. /**
  10.  * 检查v1、v2是否属于同一集合
  11.  */
  12. public boolean isSame(int v1, int v2);

isSame（）

  1. public boolean isSame(int v1, int v2){
  2. 	return find(v1) == find(v2);
  3. }

六、抽象类

这是个并查集的抽象类，后面的所有并查集都将继承它。

  1. package union;
  2.  
  3. /**
  4.  * 这是个并查集的抽象类，后面的所有并查集都将继承它。
  5.  */
  6. public abstract class UnionFind {
  7. //    初始一维数组存放父节点
  8.     protected int[] parents;
  9.     //初始化
  10.     public UnionFind(int capacity){
  11.         if (capacity<0){
  12.             throw new IllegalArgumentException("capacity must be >=1");
  13.         }
  14. //        创建一个capacity的数组容量大小存放父节点
  15.         parents=new int[capacity];
  16.         //将初始化，自己作为父节点
  17.         for (int i=0;i<parents.length;i++){
  18.             parents[i]=i;
  19.         }
  20.     }
  21.  
  22.     public abstract void union(int v1,int v2);
  23.  
  24.     /**
  25.      * 检查v1，v2是否属于同一个集合
  26.      * @param v1
  27.      * @param v2
  28.      * @return
  29.      */
  30.     public boolean isSame(int v1,int v2){
  31.         return find(v1)==find(v2);
  32.     }
  33.  
  34.     /**
  35.      * 查找v所属的集合（根节点）
  36.      * @param v
  37.      * @return
  38.      */
  39.     public abstract int find(int v);
  40.  
  41. //    判断v是否越界
  42.     protected void rangeCheck(int v){
  43.         if (v<0 || v>=parents.length){
  44.             throw new IllegalArgumentException("v is out of bounds");
  45.         }
  46.     }
  47. }

六、Quick Find【v1 所在集合的所有元素都指向 v2 的根节点】

1.Union

1.Union图解

2.注意点： 

1）将v1的根节点修改成v2的根节点，同时要将v1的根节点的根节点全部修改为v2的根节点。

2）union 时间复杂度：O(n)

3）树的高度最高为2

3.代码实现

  1. /**
  2.  * 将v1所在集合的所有元素都嫁接到v2的父节点上
  3.  * v1    v2   union(v1,v2)
  4.  *  0    4	     4
  5.  * 1 2   3     0 1 2 3
  6.  */
  7. public void union(int v1, int v2){
  8. 	int p1 = parents[v1];
  9. 	int p2 = parents[v2];
  10. 	
  11. 	for (int i = 0; i < parents.length; i++) {
  12. 		if(parents[i] == p1){
  13. //如果跟p1是同一个父节点，则将其父节点修改为p2的
  14. 			parents[i] = p2;
  15. 		}
  16. 	}
  17. }

2.find 

1.find图解

2.代码实现

  1.     /**
  2.      * 查找v所属的集合（根节点）
  3.      * @param v
  4.      * @return
  5.      */
  6.     public int find(int v){
  7.         rangeCheck(v);
  8.         return parents[v];
  9.     }

3.完整代码

UnionFind_QuickFind 

  1. package union;
  2.  
  3. /**
  4.  * 查找（Find）的时间复杂度：O(1)
  5.  * 合并（Union）的时间复杂度：O(n)
  6.  */
  7.  
  8. public class UnionFind_QuickFind extends UnionFind{
  9.     public UnionFind_QuickFind(int capacity) {
  10.         super(capacity);
  11.     }
  12.  
  13.     /**
  14.      * 查找v所属的集合（根节点）
  15.      * @param v
  16.      * @return
  17.      */
  18.     public int find(int v){
  19.         rangeCheck(v);
  20.         return parents[v];
  21.     }
  22.     public void union(int v1,int v2){
  23. //        p1:表示v1的父节点
  24.         int p1=find(v1);
  25. //        p2：表示v2的父节点
  26.         int p2=find(v2);
  27.         if (p1==p2) return;
  28.  
  29. //        到此处则v1和v2不是同一个父节点
  30.         for (int i=0;i<parents.length;i++){
  31. //            遍历所有的父节点，如果该父节点和v1表示，要将其全部修改为v2的父节点（p2）
  32.             if (parents[i]==p1){
  33.                 parents[i]=p2;
  34.             }
  35.         }
  36.     }
  37. }

七、（常用）Quick Union【v1 的根节点指向 v2 的根节点】

1.Union

1.注意点

1）Quick Find 的 union(v1, v2)：让 v1 所在集合的所有元素都指向 v2 的根节点。

2）Quick Union 的 union(v1, v2)：让 v1 的根节点指向 v2 的根节点 。(与Quick Find进行对比)

3）树的最大高度超过2

2.Quick Union图解

 

3.代码实现

  1. /**
  2.  * 将v1的根节点嫁接到v2的根节点上
  3.  */
  4.     @Override
  5.     public void union(int v1, int v2) {
  6.         int p1=find(v1);
  7.         int p2=find(v2);
  8.         if (p1==p2){
  9.             return;
  10.         }
  11. //        将p1指向p2的父节点【也就是p1的父节点为p2的父节点】
  12.         parents[p1]=p2;
  13.     }

2.find

当当前节点值和父节点的值相等的时候，说明该节点是根节点【v==parents[i]】

代码实现

  1.    /**
  2.      * 通过parents链表不断向上查找，直到根节点
  3.      * @param v
  4.      * @return
  5.      */   
  6.  @Override
  7.     public int find(int v) {
  8.         rangeCheck(v);
  9.         //当v不跟父节点的值相等，则表示还未找到根节点
  10.         while (v!=parents[v]){
  11.             v=parents[v];
  12.         }
  13.         return v;
  14.     }

3.完整代码

QuionFind_QuickUnion
  1. package union;
  2.  
  3. /**
  4.  * 查找（Find）的时间复杂度：O(logn), 可以优化至 O(
    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/836018?site
    推荐阅读
    相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。