java编程实现并查集的路径压缩代码详解

首先看两张路径压缩的图片：

并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

使用并查集时，首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ，一般都会使用一个整数表示集合中的一个元素。
每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。

并查集的基本操作有三个：

makeSet(s)：建立一个新的并查集，其中包含 s 个单元素集合。
unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
find(x)：找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。

package com.dataStructure.union_find;

// 我们的第五版Union-Find
public class UnionFind5 {

  // rank[i]表示以i为根的集合所表示的树的层数
  // 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
  // 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
  private int[] rank;
  private int[] parent; // parent[i]表示第i个元素所指向的父节点
  private int count;  // 数据个数

  // 构造函数
  public UnionFind5(int count){
    rank = new int[count];
    parent = new int[count];
    this.count = count;
    // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
    for( int i = 0 ; i < count ; i ++ ){
      parent[i] = i;
      rank[i] = 1;
    }
  }

  // 查找过程, 查找元素p所对应的集合编号
  // O(h)复杂度, h为树的高度
  private int find(int p){
    assert( p >= 0 && p < count );

    // path compression 1
    while( p != parent[p] ){
      parent[p] = parent[parent[p]];
      p = parent[p];
    }
    return p;

    // path compression 2, 递归算法
//      if( p != parent[p] )
//        parent[p] = find( parent[p] );
//      return parent[p];
  }

  // 查看元素p和元素q是否所属一个集合
  // O(h)复杂度, h为树的高度
  public boolean isConnected( int p , int q ){
    return find(p) == find(q);
  }

  // 合并元素p和元素q所属的集合
  // O(h)复杂度, h为树的高度
  public void unionElements(int p, int q){

    int pRoot = find(p);
    int qRoot = find(q);

    if( pRoot == qRoot )
      return;

    // 根据两个元素所在树的元素个数不同判断合并方向
    // 将元素个数少的集合合并到元素个数多的集合上
    if( rank[pRoot] < rank[qRoot] ){
      parent[pRoot] = qRoot;
    }
    else if( rank[qRoot] < rank[pRoot]){
      parent[qRoot] = pRoot;
    }
    else{ // rank[pRoot] == rank[qRoot]
      parent[pRoot] = qRoot;
      rank[qRoot] += 1;  // 此时, 我维护rank的值
    }
  }
}

总结

以上就是本文关于java编程实现并查集的路径压缩代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Java基于递归解决全排列问题算法示例

    本文实例讲述了Java基于递归解决全排列问题算法.分享给大家供大家参考,具体如下: 排列问题 设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}.集合x中元素的全排列记为Perm(X).(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列.R的全排列可归纳如下: 当n=1时,Perm(R)=(r),其中r是集合中唯一的元素: 当n>1时,Perm(R)由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3)....(

  • Java实现的猴子吃桃问题算法示例

    本文实例讲述了Java实现的猴子吃桃问题算法.分享给大家供大家参考,具体如下: 猴子吃桃问题 概述:猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个:第二天又将剩下的桃子吃掉了一半,又多吃了一个:以后每天都吃前一天身下的一半零一个,到第n天再想吃的时候就只剩下一个桃子了,求第一天共摘了多少个桃子? 思路及演算步骤(求出共摘多少桃子的函数表达式): 离现在的天数作为变量 f(1) = 1 (剩下桃子的数目) f(2) = f(3) - (吃掉了一些) =   f(3) -(f(3)/

  • 70行Java代码实现深度神经网络算法分享

    70行Java代码实现深度神经网络算法分享

    对于现在流行的深度学习,保持学习精神是必要的--程序员尤其是架构师永远都要对核心技术和关键算法保持关注和敏感,必要时要动手写一写掌握下来,先不用关心什么时候用到--用不用是政治问题,会不会写是技术问题,就像军人不关心打不打的问题,而要关心如何打赢的问题. 程序员如何学习机器学习 对程序员来说,机器学习是有一定门槛的(这个门槛也是其核心竞争力),相信很多人在学习机器学习时都会为满是数学公式的英文论文而头疼,甚至可能知难而退.但实际上机器学习算法落地程序并不难写,下面是70行代码实现的反向多层(BP

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • Java编程实现基于用户的协同过滤推荐算法代码示例

    协同过滤简单来说是利用某兴趣相投.拥有共同经验之群体的喜好来推荐用户感兴趣的信息,个人通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的目的进而帮助别人筛选信息,回应不一定局限于特别感兴趣的,特别不感兴趣信息的纪录也相当重要. 协同过滤又可分为评比(rating)或者群体过滤(social filtering)协同过滤以其出色的速度和健壮性,在全球互联网领域炙手可热 UserCF的核心思想即为根据用户数据模拟向量相似度,我们根据这个相似度,来找出指定用户的相似用户,然后将相似用

  • java随机数生产算法实例

    java随机数生产算法实例

    java提供了Math.random()函数,返回一个double类型的随机数,也有util包里的Random类,可以生成double,int,float,long,bytes等随机数. 但有些业务需求,往往需要对这些方法做一下封装.比如用固定因子生成32位的3DES算法key值. 下面提供一些封装的方法: package test; import java.util.Random; public class RandomUtil { public static final String ALL

  • Java实现的求逆矩阵算法示例

    Java实现的求逆矩阵算法示例

    本文实例讲述了Java实现的求逆矩阵算法.分享给大家供大家参考,具体如下: package demo; public class MatrixInverse { public static double Det(double [][]Matrix,int N)//计算n阶行列式(N=n-1) { int T0; int T1; int T2; double Num; int Cha; double [][] B; if(N>0) { Cha=0; B=new double[N][N]; Num=

  • Java求10到100000之间的水仙花数算法示例

    Java求10到100000之间的水仙花数算法示例

    本文实例讲述了Java求10到100000之间的水仙花数算法.分享给大家供大家参考,具体如下: 水仙花数: 概念:水仙花数是指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身.(例如:1^3 + 5^3+ 3^3 = 153) 算法思路分析:这个算法我们分两个步骤来进行:第一:我们做一个求一个数的位数的函数:第二:我们通过调用此函数来进行10到100000之间素数的计算! 下面给出具体的代码(仅供参考): package javastudy; public class

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • java编程无向图结构的存储及DFS操作代码详解

    java编程无向图结构的存储及DFS操作代码详解

    图的概念 图是算法中是树的拓展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),从上向下排列.而图没有了父子结点的概念,图中的结点都是平等关系,结果更加复杂. 无向图                                                       有向图 图G=(V,E),其中V代表顶点Vertex,E代表边edge,一条边就是一个定点对(u,v),其中(u,v)∈V. 这两天遇到一个关于图的算法,在网上找了很久没有找到java版的关于数据结构中图的存储及其

  • java使用RSA与AES加密解密的实例代码详解

    首先了解下,什么是堆成加密,什么是非对称加密? 对称加密:加密与解密的密钥是相同的,加解密速度很快,比如AES 非对称加密:加密与解密的秘钥是不同的,速度较慢,比如RSA •先看代码(先会用在研究) 相关依赖: <dependency> <groupId>org.bouncycastle</groupId> <artifactId>bcprov-jdk15on</artifactId> <version>1.58</versio

  • Java 添加Word目录的2种方法示例代码详解

    目录是一种能够快速.有效地帮助读者了解文档或书籍主要内容的方式.在Word中,插入目录首先需要设置相应段落的大纲级别,根据大纲级别来生成目录表.本文中生成目录分2种情况来进行: 1.文档没有设置大纲级别,生成目录前需要手动设置 2.文档已设置大纲级别,通过域代码生成目录 使用工具: •Free Spire.Doc for Java 2.0.0 (免费版) •IntelliJ IDEA 工具获取途径1:通过官网下载jar文件包,解压并导入jar文件到IDEA程序. 工具获取途径2:通过Maven仓

  • JAVA错误类结果类和分页结果类代码详解

    这篇文章主要介绍了JAVA错误类结果类和分页结果类代码详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 public interface ErrorCode { String getCode(); String getMsg(); /** * 公共错误码<br/> * 码段:10000~10099 * * */ public enum CommonError implements ErrorCode { SUCCESS("

  • java中的前++和后++的区别示例代码详解

    java中的前加加++和后加加++,有很多人搞的很晕,不太明白!今天我举几个例子说明下前++和后++的区别! 其实大家只要记住一句话就可以了,前++是先自加再使用而后++是先使用再自加! 前++和后++总结:其实大家只要记住一句话就可以了,前++是先自加再使用而后++是先使用再自加! 请大家看下面的例子就明白了! public class Test { public static void main(String[] args) { //测试,前加加和后加加 //前++和后++总结:其实大家只要

  • C语言并查集的非递归实现详解

    目录 [算法分析] [算法代码] 并查集压缩路径非递归写法 参考文章 总结 [算法分析] 经典的递归实现的并查集,在数据规模过大时,可能会爆栈,因此有了并查集的非递归实现.核心代码如下: int find(int x) { int t=x; while(t!=pre[t]) t=pre[t]; while(x!=pre[x]) { x=pre[x]; pre[x]=t; } return t; } void merge(int x,int y) { if(find(x)!=find(y)) pr

  • Java编程中最基础的文件和目录操作方法详解

    文件操作 平常经常使用JAVA对文件进行读写等操作,这里汇总一下常用的文件操作. 1.创建文件 public static boolean createFile(String filePath){ boolean result = false; File file = new File(filePath); if(!file.exists()){ try { result = file.createNewFile(); } catch (IOException e) { e.printStack

  • Java Rabbitmq中四种集群架构的区别详解

    Java Rabbitmq中四种集群架构的区别详解

    目录 主备模式 远程模式 镜像模式 多活模式 Federation插件 总结 Rabbitmq 四种集群架构 1. 主备模式 2. 远程模式3. 镜像模式  4. 多活模式 主备模式 主备模式: warren 兔子窝 一个主.一个备方案 主节点如果挂了 从节点提供服务 和Activemq 利用zk 做主/备一样 主备模式 ----------------------->HaProxy 配置 listen rabbitmq_cluster bind 0.0.0.0:5682 # 配置tcp 模式

  • java比较两个list是否相同equals的代码详解

    比较两个list是否相同,一般我用数组自带的函数equals,如: public int updateTemplateByVO(ContentTemplateVO contentTemplateVO) throws Exception { int flag = 0; if (null == contentTemplateVO) { return flag; } //比较新编辑的模板参数是否与原有的参数相同 //新的参数数组 List<String> stringList = getParamL

随机推荐