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

目录
  • 概念
  • 实现
    • 初始化并查集
    • 判断是不是同一个组
    • 查找当前节点的代表节点
    • 合并操作

本期文章源码:GitHub

一文彻底搞懂《并查集》!

概念

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。比如说,我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。

具体的用法,我们会以下一篇文章《图的相关算法》中,有一个克鲁斯卡尔算法,用于生成最小生成树,会用到并查集。

并查集的主要作用是求连通分支数(如果一个图中所有点都存在可达关系(直接或间接相连),则此图的连通分支数为1;如果此图有两大子图各自全部可达,则此图的连通分支数为2……)

在现实生活中,也是存在着并查集的一些概念,例如最近《天龙八部》里的人物关系,可能你并不认识丐帮的一些小人物,但是你一定认识丐帮帮主乔峰。当你看见一个叫花子,你就会想到他的老大就是帮主乔峰,像这样的场景,就有了一定的归属感, 会自动的认为叫花子就是跟丐帮合并在一起的……

说简单一点,并查集就是将一些数据进行分类,这样数据为一组,那些数据为另一组。如何判断其中两个数据,在不在一个组?我们就会去找每个组的代表,看这两个数据的代表是不是同一个?如果是,那就是在一个组;如果不是,那就不在一个组。所以并查集的大致框架就是下面这样:

//并查集大致框架---代码中的数据(Node),可以是其他,比如二叉树节点、图的边、节点等等 抽象的数据
public class UnionSet {
    private HashMap<Node, Node> fatherMap; //key表示当前这个数据,value表示这个数据的代表(父亲)是谁
    private HashMap<Node, Integer> sizeMap; //表示当前这个组(集合)的大小

    public UnionSet() { //构造方法
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
    }

    public void makeSet(List<Node> list) { //生成初始化状态的并查集,刚开始每个数据都是独立的

    }

    public boolean isSameSet(Node node1, Node node2) { //判断当前这两个数据,是不是一个组的?

    }

    private Node findFather(Node node) { //查找这个数据,它那个组的代表(父亲)是谁?

    }

    public void union(Node node1, Node node2) { //将这两个数据,放到一个组

    }
}

上面就是大致的框架,就是几个方法:初始化并查集、判断是不是一个组、查找代表、合并到一个组。四个方法,就是并查集。简不简单?

并查集在判断两个数据,是否在一个组时,时间复杂度能做到O(1),所以这种数据结构还是非常有用的。

实现

初始化并查集

我们首先从第一个方法:初始化并查集开始。

传入进去的参数不一定是List,也可以是Collection等等,表示一组数据即可! 首先我们的成员变量只有两个,分别是存储节点的代表 和 当前这个组的大小。初始化时,我们分别认为 每个节点是自己一个人一组的,也就是说,自己一个组,代表就是自己本身;大小的话,就是自己本身咯,也就是1。

//初始化并查集
public void makeSet(List<Node> list) {
    if (list == null) {
        return;
    }
    fatherMap.clear();
    sizeMap.clear(); //先将表清空

    //遍历list,把每一个节点,都放入哈希表中
    for (Node node : list) {
        fatherMap.put(node, node); //第一个参数是节点本身,第二个参数就是这个组的代表
        sizeMap.put(node, 1); //第一个参数是这个组的代表,第二个参数是大小
    }
}

判断是不是同一个组

isSameSet 比较简单,就是判断两个数据所在的组的代表,是不是用一个数据即可!如果代表是同一个人,那就是在一个组,反之就不是!

//判断是不是同一个组
public boolean isSameSet(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return false;
    }
    return findFather(node1) == findFather(node2); //查找各自的代表节点,看是不是同一个。
}

查找当前节点的代表节点

findFather,我自己觉得算是并查集的核心,也这是这个方法,是并查集的查找的时间复杂度能在O(1)的主要因素。

思路就跟二叉树向上查找根结点的思路一样,也就是说,在fatherMap中一直查找,直到一个节点的代表节点(父节点)是它自己本身时,此时就查找完了;然后最关键的一步,就是路径压缩,在我们向上查找的过程中,我们需要记录沿途的所有节点,在查找结束后,我们将沿途的这些节点,在fatherMap中的进行修改,直接将这些节点的代表节点,写成这个组的代表节点,可能听糊涂了,看下图:

这样的设计,就能使查找的时间复杂度控制在O(1)。

//查找代表节点,并做路径压缩
private Node findFather(Node node) {
    if (node == null) {
        return null;
    }
    //查找代表节点
    Stack<Node> path = new Stack<>(); //存储沿途的节点
    while (node != fatherMap.get(node)) { //代表节点不是自己本身,就继续查找
        path.push(node);
        node = fatherMap.get(node);
    }
    //路径压缩
    while (!path.isEmpty()) {
        Node tmp = path.pop();
        fatherMap.put(tmp, node); //此时的node,就是这个组的代表节点
    }

    return node;
}

合并操作

终于来到了最后的操作:合并。合并也比较简单,记住一个要点:小组挂在大组的下面。也就是说,这一个节点所在的组要小一点,我们直接将他“挂”在另一个组的下面。说简单一点:这一个组的代表节点的vaule域,直接指向另一个组的代表节点。

//合并操作
public void union(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    int node1Size = sizeMap.get(node1);
    int node2Size = sizeMap.get(node2); //分别得到两个节点所在组的大小
    Node node1Father = fatherMap.get(node1);
    Node node2Father = fatherMap.get(node2); //分别拿到两个节点的代表节点

    if (node1Father != node2Father) { //两个节点,不在同一个组,就合并
        if (node1Size < node2Size) { //node1 挂在 node2
            fatherMap.put(node1Father, node2Father);
            sizeMap.put(node2Father, node1Size + node2Size); //新的组,大小是原来两个组的和
            sizeMap.remove(node1Father); //小组的数据,就不需要了,删除
        } else { //node2 挂在 node1
            //跟上面操作类似
            fatherMap.put(node2Father, node1Father);
            sizeMap.put(node1Father, node1Size + node2Size);
            sizeMap.remove(node1Father);
        }
    }
}

上面就是并查集的所有操作了,是不是很简单呢?

好啦,本期更新到此就结束啦,同学们,下期见!!!

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

时间: 2021-09-15

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

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

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使用HashMap实现并查集

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

Java实现快速并查集

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

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

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

使用docker快速搭建Spark集群的方法教程

前言 Spark 是 Berkeley 开发的分布式计算的框架,相对于 Hadoop 来说,Spark 可以缓存中间结果到内存而提高某些需要迭代的计算场景的效率,目前收到广泛关注.下面来一起看看使用docker快速搭建Spark集群的方法教程. 适用人群 正在使用spark的开发者 正在学习docker或者spark的开发者 准备工作 安装docker (可选)下载java和spark with hadoop Spark集群 Spark运行时架构图 如上图: Spark集群由以下两个部分组成 集

数据结构与算法之并查集(不相交集合)

认识并查集 对于并查集(不相交集合),很多人会感到很陌生,没听过或者不是特别了解.实际上并查集是一种挺高效的数据结构.实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来. 对于定意义,百科上这么定义的: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在

C++并查集亲戚(Relations)算法实例

本文实例讲述了C++并查集亲戚(Relations)算法.分享给大家供大家参考.具体分析如下: 题目: 亲戚(Relations) 或许你并不知道,你的某个朋友是你的亲戚.他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子.如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及.在这种情况下,最好的帮手就是计算机. 为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,Tom和B en是

java中快速创建带初始值的List和Map实例

初始化一个List和Map对象并为期加入值的写法如下: List<String> sList = new ArrayList<String>(); sList.add("str1"); sList.add("str2"); Map<String,String> sMap = new HashMap<String, String>(); sMap.put("k1", "v1");

python实现一个简单的并查集的示例代码

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题.常常在使用中以森林来表示. 并查集有三种基本操作,获得根节点,判断两节点是否连通,以及将两不连通的节点相连(相当于将两节点各自的集合合并) 用UnionFind类来表示一个并查集,在构造函数中,初始化一个数组parent,parent[i]表示的含义为,索引为i的节点,它的直接父节点为parent[i].初始化时各个节点都不相连,因此初始化parent[i]=i,让自己成为自己的父节点,从而实现各节点不互连. def __ini

c++初级并查集知识点总结

并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题. 有一个联合- 查找算法定义了两个用于此数据结构的操作: Find :确定元素属于哪一个子集.它可以被用来确定两个元素是否属于同一子集. Union:将两个子集合并成同一个集合. 并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题,在信息学竞赛中广泛涉及 初始化: 一开始,每一个元素都是一个集合,打个比方,每个人所在的 " 家族 " 只有他一个人.我们还需要一个 f 数组,里面存的是他的 "父亲&quo