图论02-并查集的实现(Java)

这篇具有很好参考价值的文章主要介绍了图论02-并查集的实现(Java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2.并查集理论基础

  • 并查集的作用
将两个元素添加到一个集合中。
判断两个元素在不在同一个集合
  • 并查集的实现

图论02-并查集的实现(Java),算法学习,图论,java

1.DSU 类定义:DSU 类中包含一个整型数组 s 用来存储元素的父节点信息。

2.DSU 构造函数:
构造函数 DSU(int size) 接受一个参数 size,初始化了大小为 size 的并查集。
在构造函数中,数组 s 被初始化为一个大小为 size 的数组,初始时每个节点的父节点是自己。
find 方法:

3.find(int x) 方法用于查找元素 x 所在集合的根节点(即代表元素)。
如果 x 的父节点等于自己,则说明 x 就是根节点,直接返回 x。
否则递归调用 find 方法,找到 x 的父节点的根节点并返回。

4.union 方法:
union(int x, int y) 方法用于合并元素 x 和元素 y 所在的两个集合。
在该实现中,直接将 x 的父节点设置为 y,即将 x 所在集合的根节点指向 y 所在集合的根节点。

Java代码实现文章来源地址https://www.toymoban.com/news/detail-843360.html

public class DSU {
    int[] s;

    /**
     * 初始化并查集,指定大小,并将每个元素初始化为自己的父节点。
     * @param size 并查集的大小。
     */
    public DSU(int size) {
        s = new int[size];
        for (int i = 0; i < s.length; i++) {
            s[i] = i;
        }
    }

    /**
     * 查找操作,用于查找包含元素 x 的集合的根/父节点。
     * @param x 要查找的元素。
     * @return 包含 x 的集合的根节点。
     */
    public int find(int x) {
        if (x == s[x]) {
            return x;
        }
        return find(s[x]);
    }

    /**
     * 合并操作,用于合并包含元素 x 和 y 的集合。
     * @param x 第一个元素。
     * @param y 第二个元素。
     */
    public void union(int x, int y) {
        s[x] = y;
    }
}
x = set.find(2);//找2节点的代表节点
y = set.find(3);//找3节点的代表节点
if (x != y) {//当二者没有相同的代表节点表明二者不在同一个集合之中,可以连接
	set.union(x, y);
}
  • 路径压缩
原因:在普通的并查集中,通过不断向上查找父节点的方式找到根节点,这可能导致树的深度较大,从而影响查找操作的效率。路径压缩通过在查找时将节点直接连接到根节点,减少了树的深度,提高了查找操作的效率。
方法:我们可以在查找父节点的时候,我们通过向上查找便可以知道谁是自己的父节点,相比直接返回父节点,我们可以顺便将自己指向父节点,这样可以降低树的深度
public int find(int x) {
        if (x == s[x]) {
            return x;
        }
        return s[x] = find(s[x]);
    }
  • 优化后完整代码
DSU(int size) 构造函数:初始化并查集,创建了两个数组 s 和 size,分别用来存储集合中各点的关系和判断不同集合的大小。在初始化过程中,将每个节点的值初始化为索引的值,表示每个节点最初都是一个独立的集合,大小为1find(int x) 方法:查找元素 x 的根节点。通过递归地查找 x 的父节点,直到找到根节点为止。在查找的过程中,进行路径压缩操作,将沿途经过的节点直接指向根节点,从而降低树的深度,优化后续查找操作的效率。

union(int x, int y) 方法:合并两个集合。在合并操作中,首先根据两个集合的大小判断,让元素较少的集合指向元素较多的集合,以减小树的深度。然后更新集合的大小信息,确保合并后大集合的大小正确反映合并前两个集合的大小之和。
public class DSU {
    int[] s;//用来存储集合中各点的关系
    int[] size;//用来判断不同集合的大小

    public DSU(int size) {//初始化并查集
        s = new int[size];
        this.size = new int[size];
        for (int i = 0; i < s.length; i++) {
            s[i] = i;//将每个节点的值初始化为索引的值
            this.size[i] = 1;//此时每个索引代表一个集合,因此集合数目为1
        }
    }

    public int find(int x) {//查找元素x的根节点
        if (x == s[x]) {//如果节点的索引与节点的值一样,说明找到节点
            return x;
        }
        //如果不相等,根据值去找根节点,因为值记录的是根节点的位置
        //路径压缩:寻找根节点的难度会随着树的深度而不断增大,所以若找到根节点,直接将根节点的值赋值给x索引的值,从而降低树的深度
        return s[x] = find(s[x]);
    }

    public void union(int x, int y) {//合并两个集合
        //在进行查找根节点的时候,会从一个节点的值不断寻找
        //对于一个集合数目大的元素,查找起来更加费时,如果
        //让大的集合指向小的集合,会使树的深度再次增加,加大
        //复杂度,因此我们需要判断连个集合的大小,让小集合指向大集合
        if (size[x] < size[y]) {//判断集合的大小
            int temp = y;
            y = x;
            x = temp;
        }
        //x表示大集合,y表示小集合
        s[y] = x;//y集合的父节点为x
        size[x] = size[x] + size[y];//此时大集合的大小为原大集合的大小加小集合的大小
    }

    @Override
    public String toString() {
        return Arrays.toString(s);
    }
}

到了这里,关于图论02-并查集的实现(Java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构--并查集的进一步优化

    压缩路径 − − F i n d 操作,先找到根节点,再将查找路径上所有结点都挂到根结点下 color{red}压缩路径 -- Find操作,先找到根节点,再将查找路径上所有结点都挂到根结点下 压缩路径 − − F in d 操作,先找到根节点,再将查找路径上所有结点都挂到根结点下 每次Find操作,

    2024年02月15日
    浏览(10)
  • 【算法每日一练]-图论(保姆级教程篇7 最小生成树 ,并查集模板篇)#村村通 #最小生成树

    目录 题目:村村通 并查集  题目:最小生成树 kruskal算法 prim算法          先引入问题: 要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的 任意两个之间都可以通信 ,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要 使铺设光

    2024年02月04日
    浏览(27)
  • 并查集算法实现

    牛客测试链接 并查集(Disjoint Set)是一种用于处理集合合并与查询问题的数据结构。它支持两种操作:合并(Union)和查询(Find)。 合并操作将两个不相交的集合合并为一个集合,查询操作用于判断两个元素是否属于同一个集合。 本文将介绍并查集算法的实现,并给出一个

    2024年01月25日
    浏览(12)
  • 代码随想录图论并查集 第七天 | 685.冗余连接II

    代码随想录图论并查集 第七天 | 685.冗余连接II 一、685.冗余连接II 题目链接:https://leetcode.cn/problems/redundant-connection-ii/ 思路:684.冗余连接中是连通且无环的无向图可直接使用并查集模板,如果想判断集合中是否有环,且那条边构成环,只需要每次加入并查集之前先判断一下是

    2024年02月06日
    浏览(11)
  • 求无向图的最小生成树——Kruskal算法(超详细)【并查集,python实现】

    以如下无向图为例,求最小生成树及其权值。 补充知识点: 最小生成树(不官方的解释):包含所有节点,保持整个图连通,所有边权值之和最小。 1、补充在前 (1)图的存储 采用二维列表存储(点,点,边的权值) (2)顶点转换 为了便于计算,将字母A ~ G用数字0 ~ 6代

    2024年02月04日
    浏览(10)
  • 【数据结构与算法】并查集

    并查集是一个树形结构,所谓的并查,就是 当我们有了一个节点,我们就能知道这个节点属于哪个集合 。 举个例子理解以下:战国时期有很多国家,它们会互相打仗,那么现在有两个互相不认识的人,如何知道对方是敌是友呢? 现在有一种方法:每个国家都有一个大王,我

    2023年04月15日
    浏览(8)
  • Peter算法小课堂—并查集

    我们先来看太戈编程467题 攀亲戚 题目描述: 最近你发现自己和古代一个皇帝长得很像:都有两个鼻子一个眼睛,你想知道这皇帝是不是你的远方亲戚,你是不是皇亲国戚。目前你能掌握的信息有m条,关于n个人:第i条信息包含两个人的编号ai,bi,表示ai和bi是亲戚。你的编号

    2024年01月18日
    浏览(14)
  • 算法与数据结构(九)--并查集

    1.处理对象:Disjoint Set,即“不相交集合”。 在一些应用问题中,需将n个不同的元素划分成一组不相交的集合。开始时,每个元素自成一个单元素集合,然后按一定顺序将属于同一组元素的集合合并。其间要反复用到查询某个元素属于哪个集合的运算。适合于描述这类问题的

    2024年02月10日
    浏览(10)
  • 算法刷题day34:并查集

    今天写的题集是并查集,其实感觉有两个难点,一个是,要维护多余的信息和路径压缩,另一个难点则是抽象出来合并集合的这个操作,还是要不断地练习,看别人怎么去做,加油! 标签:并查集 思路: 模板题,没啥说的 题目描述: 示例代码: 标签:并查集 思路: 其实

    2024年03月21日
    浏览(22)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包