java 数据结构并查集详解
一、概述
并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题。例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄
两大核心:
查找 (Find) : 查找元素所在的集合
合并 (Union) : 将两个元素所在集合合并为一个集合
二、实现
并查集有两种常见的实现思路
快查(Quick Find)
- 查找(Find)的时间复杂度:O(1)
- 合并(Union)的时间复杂度:O(n)
快并(Quick Union)
- 查找(Find)的时间复杂度:O(logn)可以优化至O(a(n))a(n)< 5
- 合并(Union)的时间复杂度:O(logn)可以优化至O(a(n))a(n)< 5
使用数组实现树型结构,数组下标为元素,数组存储的值为父节点的值
创建抽象类Union Find
public abstract class UnionFind { int[] parents; /** * 初始化并查集 * @param capacity */ public UnionFind(int capacity){ if(capacity < 0) { throw new IllegalArgumentException("capacity must be >=0"); } //初始时每一个元素父节点(根结点)是自己 parents = new int[capacity]; for(int i = 0; i < parents.length;i++) { parents[i] = i; } } /** * 检查v1 v2 是否属于同一个集合 */ public boolean isSame(int v1,int v2) { return find(v1) == find(v2); } /** * 查找v所属的集合 (根节点) */ public abstract int find(int v); /** * 合并v1 v2 所属的集合 */ public abstract void union(int v1, int v2); // 范围检查 public void rangeCheck(int v) { if(v<0 || v > parents.length) throw new IllegalArgumentException("v is out of capacity"); } }
2.1 Quick Find实现
以Quick Find实现的并查集,树的高度最高为2,每个节点的父节点就是根节点
public class UnionFind_QF extends UnionFind { public UnionFind_QF(int capacity) { super(capacity); } // 查 @Override public int find(int v) { rangeCheck(v); return parents[v]; } // 并 将v1所在集合并到v2所在集合上 @Override public void union(int v1, int v2) { // 查找v1 v2 的父(根)节点 int p1= find(v1); int p2 = find(v2); if(p1 == p2) return; //将所有以v1的根节点为根节点的元素全部并到v2所在集合上 即父节点改为v2的父节点 for(int i = 0; i< parents.length; i++) { if(parents[i] == p1) { parents[i] = p2; } } } }
2.2 Quick Union实现
public class UnionFind_QU extends UnionFind { public UnionFind_QU(int capacity) { super(capacity); } //查某一个元素的根节点 @Override public int find(int v) { //检查下标是否越界 rangeCheck(v); // 一直循环查找节点的根节点 while (v != parents[v]) { v = parents[v]; } return v; } //V1 并到 v2 中 @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //将v1 根节点 的 父节点 修改为 v2的根结点 完成合并 parents[p1] = p2; } }
三、优化
并查集常用快并来实现,但是快并有时会出现树不平衡的情况
有两种优化思路:rank优化,size优化
3.1基于size的优化
核心思想:元素少的树 嫁接到 元素多的树
public class UniondFind_QU_S extends UnionFind{ // 创建sizes 数组记录 以元素(下标)为根结点的元素(节点)个数 private int[] sizes; public UniondFind_QU_S(int capacity) { super(capacity); sizes = new int[capacity]; //初始都为 1 for(int i = 0;i < sizes.length;i++) { sizes[i] = 1; } } @Override public int find(int v) { rangeCheck(v); while (v != parents[v]) { v = parents[v]; } return v; } @Override public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; //如果以p1为根结点的元素个数 小于 以p2为根结点的元素个数 p1并到p2上,并且更新p2为根结点的元素个数 if(sizes[p1] < sizes[p2]) { parents[p1] = p2; sizes[p2] += sizes[p1]; // 反之 则p2 并到 p1 上,更新p1为根结点的元素个数 }else { parents[p2] = p1; sizes[p1] += sizes[p2]; } } }
基于size优化还有可能会导致树不平衡
3.2基于rank优化
核心思想:矮的树 嫁接到 高的树
public class UnionFind_QU_R extends UnionFind_QU { // 创建rank数组 ranks[i] 代表以i为根节点的树的高度 private int[] ranks; public UnionFind_QU_R(int capacity) { super(capacity); ranks = new int[capacity]; for(int i = 0;i < ranks.length;i++) { ranks[i] = 1; } } public void union(int v1, int v2) { int p1 = find(v1); int p2 = find(v2); if(p1 == p2) return; // p1 并到 p2 上 p2为根 树的高度不变 if(ranks[p1] < ranks[p2]) { parents[p1] = p2; // p2 并到 p1 上 p1为根 树的高度不变 } else if(ranks[p1] > ranks[p2]) { parents[p2] = p1; }else { // 高度相同 p1 并到 p2上,p2为根 树的高度+1 parents[p1] = p2; ranks[p2] += 1; } } }
基于rank优化,随着Union次数的增多,树的高度依然会越来越高 导致find操作变慢
有三种思路可以继续优化 :路径压缩、路径分裂、路径减半
3.2.1路径压缩(Path Compression )
在find时使路径上的所有节点都指向根节点,从而降低树的高度
/** * Quick Union -基于rank的优化 -路径压缩 * */ public class UnionFind_QU_R_PC extends UnionFind_QU_R { public UnionFind_QU_R_PC(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); if(parents[v] != v) { //递归 使得从当前v 到根节点 之间的 所有节点的 父节点都改为根节点 parents[v] = find(parents[v]); } return parents[v]; } }
虽然能降低树的高度,但是实现成本稍高
3.2.2路径分裂(Path Spliting)
使路径上的每个节点都指向其祖父节点
/** * Quick Union -基于rank的优化 -路径分裂 * */ public class UnionFind_QU_R_PS extends UnionFind_QU_R { public UnionFind_QU_R_PS(int capacity) { super(capacity); } @Override public int find(int v) { rangeCheck(v); while(v != parents[v]) { int p = parents[v]; parents[v] = parents[parents[v]]; v = p; } return v; } }
3.2.3路径减半(Path Halving)
使路径上每隔一个节点就指向其祖父节点
/** * Quick Union -基于rank的优化 -路径减半 * */ public class UnionFind_QU_R_PH extends UnionFind_QU_R { public UnionFind_QU_R_PH(int capacity) { super(capacity); } public int find(int v) { rangeCheck(v); while(v != parents[v]) { parents[v] = parents[parents[v]]; v = parents[v]; } return v; } }
使用Quick Union + 基于rank的优化 + 路径分裂 或 路径减半
可以保证每个操作的均摊时间复杂度为O(a(n)) , a(n) < 5
到此这篇关于java 数据结构并查集详解的文章就介绍到这了,更多相关java 并查集内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/qq_52595134/article/details/122829762
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了C#数据结构之队列(Quene),结合实例形式较为详细的讲述了队列的功能、原理与C#实现队列的相关技巧,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19