Java数据结构之并查集的实现

目录
  • 代码解析
  • 代码应用
  • 实际应用

并查集就是将原本不在一个集合里面的内容合并到一个集合中。

在实际的场景中用处不多。

除了出现在你需要同时去几个集合里面查询,避免出现查询很多次,从而放在一起查询的情况。

下面简单实现一个例子,我们来举例说明一下什么是并查集,以及究竟并查集解决了什么问题。

代码解析

package com.chaojilaji.book.andcheck;

public class AndCheckSet {

    public static Integer getFather(int[] father, int u) {
        if (father[u] != u) {
            father[u] = getFather(father, father[u]);
        }
        return father[u];
    }

    public static void join(int[] father,int x, int y) {
        int fx = getFather(father,x);
        int fy = getFather(father,y);
        if (fx != fy){
            father[fx] = fy;
        }
    }

    public static void main(String[] args) {
        int n = 10;
        int[] a = new int[n];
        for (int i = 0;i<n;i++){
            a[i] = i; // 初始化定义一百个集合
        }
        for (int i=0;i<n;i++){
            System.out.println(i+" "+getFather(a, i)); // 对于每个集合,父节点都是自己
        }
    }
}

首先,我们定义了两个函数,分别为getFather和join,分别表示获取u所在集合的根以及合并两个集合。

先来看看getFather方法

public static Integer getFather(int[] father, int u) {
    if (father[u] != u) {
        father[u] = getFather(father, father[u]);
    }
    return father[u];
}

是找出值u所在集合的根节点是多少。一般来说,father[u]如果等于u本身,那么说明u所在节点就是根节点,而这个算法是直到相等才退出,也就是说,对于从u到根节点的每个节点的father都被直接置为根节点,同时返回了当前节点的根节点。

然后来看看join方法

public static void join(int[] father,int x, int y) {
    int fx = getFather(father,x);
    int fy = getFather(father,y);
    if (fx != fy){
        father[fx] = fy;
    }
}

分别找出x和y两个节点所在集合的根节点,如果根节点不一样,则将其中一个节点的father节点置为另一个节点即可,这样就合并成了一个集合。

代码应用

public static void main(String[] args) {
    int n = 10;
    int[] a = new int[n];
    for (int i = 0;i<n;i++){
        a[i] = i; // 初始化定义n个集合
    }
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i)); // 对于每个集合,父节点都是自己
    }
    System.out.println("-------------------------");
    join(a,0,1); // 合并 0 和 1
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了0和1,所以集合变成了9个,节点0和节点1的根都是节点1
    System.out.println("-------------------------");
    join(a,2,3); // 合并 2 和 3
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了2和3,所以集合变成8个,节点2和节点3的根都是节点3
    System.out.println("-------------------------");
    join(a,1,3); // 合并 1 和 3
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了1和3,所以集合变成7个,节点0,1,2,3的根都是节点3
}

首先,我们定义了n个集合,这n个集合的值是0~n-1,然后此时他们的父节点均等于他们本身,所以这就是n个独立的集合,结果如下

0的父节点为 0 1的父节点为 1 2的父节点为 2 3的父节点为 3 4的父节点为 4 5的父节点为 5 6的父节点为 6 7的父节点为 7 8的父节点为 8 9的父节点为 9

然后调用 join(a,0,1)合并0集合和1集合,再输出节点父集合情况为

0的父节点为 1 1的父节点为 1 2的父节点为 2 3的父节点为 3 4的父节点为 4 5的父节点为 5 6的父节点为 6 7的父节点为 7 8的父节点为 8 9的父节点为 9

可以看见,由于合并了0和1,所以集合变成了9个,节点0和节点1的根都是节点1。
然后调用 join(a,2,3) 合并2集合和3集合,输出节点父集合情况为

0的父节点为 1 1的父节点为 1 2的父节点为 3 3的父节点为 3 4的父节点为 4 5的父节点为 5 6的父节点为 6 7的父节点为 7 8的父节点为 8 9的父节点为 9

可以看见,由于合并了2和3,所以集合变成8个,节点2和节点3的根都是节点3。
最后,我们再调用join(a,1,3) 合并1集合和3集合,输出节点父集合情况为

0的父节点为 3 1的父节点为 3 2的父节点为 3 3的父节点为 3 4的父节点为 4 5的父节点为 5 6的父节点为 6 7的父节点为 7 8的父节点为 8 9的父节点为 9

可以看出来,由于合并了1和3,所以集合变成7个,节点0,1,2,3的根都是节点3。

实际应用

代码的层面来讲,并查集很好实现。但是我们却也可以发现,其应用场景似乎非常局限。
首先,我们需要定义出一个father[x] = x的数组,然后我们再去合并。似乎很难想到应用场景。

那么我们可以想象一个场景,现在有个网络拓扑图,里面有n和网络设施设备,然后又给了你这n个设施设备之间的连接关系,问你一共有多少个局部联通网。
对于这个问题,我们就可以首先定义每个设备自己跟自己相连,然后每出现一条边,就对这两个设备采取join操作。最终我们在遍历完所有的节点,得到多少个不同的father,即表示有多少个不同的局部联通网。

这样的问题还可以延伸到我们的人际交友圈,首先每个人都是单独的集合,在不断认识人的过程中,产生连通性。最终让你确认一共有多少个不互通的人际圈。

所以你会发现,这本质上就是求图论中连通块的个数。

到此这篇关于Java数据结构之并查集的实现的文章就介绍到这了,更多相关Java并查集内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java实现快速并查集

    在一些应用的问题中,需将n个不同的元素划分成一组不相交的集合.开始时,每个元素自成一格单元素集合,然后按一定顺序将属于同一组的元素的集合合并.其间要反复用到查询某个元素属于哪个集合的运算.适合于描述这类问题的抽象数据类型称为并查集. 1. 并查集的概述 并查集的数学模型是一组不相交的动态集合的集合S={A,B,C,...},它支持以下的运算: (1)union(A,B):将集合A和B合并,其结果取名为A或B: (2)find(x):找出包含元素x的集合,并返回该集合的名字. 在并查集中需要两个类

  • Java数据机构中关于并查集的详解

    目录 概念 实现 初始化并查集 判断是不是同一个组 查找当前节点的代表节点 合并操作 本期文章源码:GitHub 一文彻底搞懂<并查集>! 概念 并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并.查).比如说,我们可以用并查集来判断一个森林中有几棵树.某个节点是否属于某棵树等. 具体的用法,我们会以下一篇文章<图的相关算法>中,有一个克鲁斯卡尔算法,用于生成最小生成树,会用到并查集. 并查集的主要作用是求连通分支数(如果一个图中所有点都存在可达关系(直

  • Java实现并查集

    本文实例为大家分享了Java实现并查集的具体代码,供大家参考,具体内容如下 自下而上的树结构 接口 /** * @author Nino */ public interface UF { int size(); /** * 看两个元素是否相连 * @param p * @param q * @return */ boolean isConnected(int p, int q); /** * 将两个元素合并在一起,变成一个集合中的元素 * @param p * @param q */ void

  • 详解Java实现数据结构之并查集

    ​一.什么是并查集 对于一种数据结构,肯定是有自己的应用场景和特性,那么并查集是处理什么问题的呢? 并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示.在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在空

  • java并查集算法带你领略热血江湖

    目录 一.什么是并查集 二.深入理解并查集 三.实现并查集 四.真题训练 五.路径压缩优化 六.总结 你好,我是小黄,一名独角兽企业的Java开发工程师. 校招收获数十个offer,年薪均20W~40W. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.什么是并查集 并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于处理一些不相交集合的合并问题,并支持两种操作: 合并

  • Java使用HashMap实现并查集

    并查集的定义: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述. 并查集是一种树型的数

  • Java实现并查集示例详解

    目录 题目 思路 find实现 join的实现 整体代码  题目 题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系. 思路 对于该题而言,考察的是并查集,也就是小怪兽逐个找上级领导的思路,指导找到最终的Boss停止下来,如果两个怪兽要打架,需要问一问他们的上级领导,领导再问领导,逐级向上,最终发现它们属于同一个Boss的部署的话就不能再打架了,这道题同样的思路,如果斗罗大陆的一开始白沉香不知道唐三是亲戚的话,他们就

  • Java数据结构之并查集的实现

    目录 代码解析 代码应用 实际应用 并查集就是将原本不在一个集合里面的内容合并到一个集合中. 在实际的场景中用处不多. 除了出现在你需要同时去几个集合里面查询,避免出现查询很多次,从而放在一起查询的情况. 下面简单实现一个例子,我们来举例说明一下什么是并查集,以及究竟并查集解决了什么问题. 代码解析 package com.chaojilaji.book.andcheck; public class AndCheckSet { public static Integer getFather(in

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

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

  • Java 数据结构进阶二叉树题集下

    目录 1.对称二叉树 2.创建并遍历二叉树 3.二叉树中两节点最近公共祖先 4.二叉搜索树与双向链表 5.根据前序和中序遍历结果创建二叉树 6.二叉树创建字符串 7.非递归实现二叉树前序遍历 8.非递归实现二叉树后序遍历 1.对称二叉树 [OJ链接] 分为以下几种情况: 二叉树为空,是对称二叉树 二叉树不为空,其左子树或者右子树为空,不是对称二叉树 二叉树不为空,左右子树都为空,是对称二叉树 二叉树不为空,左右子树不为空,左右子节点值不同,不是对称二叉树 二叉树不为空,左右子树不为空,左右子节点

  • Java 数据结构进阶二叉树题集上

    目录 1.二叉树的遍历 (1)前.中.后序遍历 (2)层序遍历 2.获取树中子结点的个数 3.获取二叉树的高度 4.判断是不是完全二叉树 5.判断两个树是否相同 6.另一棵树的子树 7.判断平衡二叉树 二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解.(上)中的题偏向于基础,后面(下)中的题机会比较难. 1.二叉树的遍历 (1)前.中.后序遍历 这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码.以前序遍历为例: 如果根节点root为

  • C++高级数据结构之并查集

    目录 1.动态连通性 2.union-find算法API 3.quick-find算法 4.quick-union算法 5.加权quick-union算法 6.使用路径压缩的加权quick-union算法 7.算法比较 前言: 高级数据结构(Ⅰ)并查集(union-find) 动态连通性 union-find算法API quick-find算法 quick-union算法 加权quick-union算法 使用路径压缩的加权quick-union算法 算法比较 并查集 > 左神版 高级数据结构(Ⅰ

  • c语言数据结构之并查集 总结

    并查集(Union-Find Set): 一种用于管理分组的数据结构.它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组. 注意:并查集不能将在同一组的元素拆分为两组. 并查集的实现: 用树来实现. 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个元素的根是否一致.显然,使用树形结构将问题简单化了.合并时是我们只需要将一组的根与另一组的根相连即可. 并查集的核心在于,一棵树的所有节点

  • java 数据结构并查集详解

    目录 一.概述 二.实现 2.1 Quick Find实现 2.2 Quick Union实现 三.优化 3.1基于size的优化 3.2基于rank优化 3.2.1路径压缩(Path Compression ) 3.2.2路径分裂(Path Spliting) 3.2.3路径减半(Path Halving) 一.概述 并查集:一种树型数据结构,用于解决一些不相交集合的合并及查询问题.例如:有n个村庄,查询2个村庄之间是否有连接的路,连接2个村庄 两大核心: 查找 (Find) : 查找元素所在

随机推荐