程序员经验分享-hwhale

【数据结构】UnionFind 并查集-2

2023-11-02

在这里插入图片描述

数据结构源码 - UnionFind1

接口

public interface UnionFind {

    int getSize();

    boolean isConnected(int p, int q);

    void unionElements(int p, int q);
}

实现类

import java.util.Random;

/**
 * 第二种UnionFind实现
 */
public class UnionFind4 implements UnionFind {

    private int[] parent;

    private int[] rank;  // rank[i]表示以i为根的集合所表示的树的层数

    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找过程，查找元素p所对应的集合编号
     * O(h)复杂度，h为树高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    /**
     * 查看元素p和元素q是否所属一个集合
     * @param p
     * @param q
     * @return
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    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[qRoot] == rank[pRoot]
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

    private static double testUF(UnionFind uf, int m) {

        int size = uf.getSize();

        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a, b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }


    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;

        UnionFind1 uf1 = new UnionFind1(size);
        System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");

        UnionFind2 uf2 = new UnionFind2(size);
        System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");

        UnionFind3 uf3 = new UnionFind3(size);
        System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");

        UnionFind4 uf4 = new UnionFind4(size);
        System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");
    }
}

数据结构拆解 - UnionFind4

维护字段和内部类


    private int[] parent;

    private int[] rank;  // rank[i]表示以i为根的集合所表示的树的层数

构造函数


    public UnionFind4(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

改



    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    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[qRoot] == rank[pRoot]
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

查



    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找过程，查找元素p所对应的集合编号
     * O(h)复杂度，h为树高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    /**
     * 查看元素p和元素q是否所属一个集合
     * @param p
     * @param q
     * @return
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

测试用例 - UnionFind4



    private static double testUF(UnionFind uf, int m) {

        int size = uf.getSize();

        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a, b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }


    public static void main(String[] args) {
        int size = 100000;
        int m = 100000;

        UnionFind1 uf1 = new UnionFind1(size);
        System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");

        UnionFind2 uf2 = new UnionFind2(size);
        System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");

        UnionFind3 uf3 = new UnionFind3(size);
        System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");

        UnionFind4 uf4 = new UnionFind4(size);
        System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");
    }

数据结构源码 - UnionFind5

接口

public interface UnionFind {

    int getSize();

    boolean isConnected(int p, int q);

    void unionElements(int p, int q);
}

实现类

import java.util.Random;

/**
 * 第二种UnionFind实现
 */
public class UnionFind5 implements UnionFind {

    private int[] parent;

    private int[] rank;  // rank[i]表示以i为根的集合所表示的树的层数

    public UnionFind5(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找过程，查找元素p所对应的集合编号
     * O(h)复杂度，h为树高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    /**
     * 查看元素p和元素q是否所属一个集合
     * @param p
     * @param q
     * @return
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    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[qRoot] == rank[pRoot]
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

    private static double testUF(UnionFind uf, int m) {

        int size = uf.getSize();

        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a, b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }


    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;

//        UnionFind1 uf1 = new UnionFind1(size);
//        System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
//
//        UnionFind2 uf2 = new UnionFind2(size);
//        System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");

        UnionFind3 uf3 = new UnionFind3(size);
        System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");

        UnionFind4 uf4 = new UnionFind4(size);
        System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");

        UnionFind5 uf5 = new UnionFind5(size);
        System.out.println("UnionFind5 : " + testUF(uf5, m) + " s");
    }
}

数据结构拆解 - UnionFind5

维护字段和内部类


    private int[] parent;

    private int[] rank;  // rank[i]表示以i为根的集合所表示的树的层数

构造函数



    public UnionFind5(int size) {
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

改

    /**
     * 合并元素p和元素q所属的集合
     * O(h)复杂度，h为树的高度
     * @param p
     * @param q
     */
    @Override
    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[qRoot] == rank[pRoot]
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

查


    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 查找过程，查找元素p所对应的集合编号
     * O(h)复杂度，h为树高度
     * @param p
     * @return
     */
    private int find(int p) {
        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    /**
     * 查看元素p和元素q是否所属一个集合
     * @param p
     * @param q
     * @return
     */
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

测试用例 - UnionFind5


    private static double testUF(UnionFind uf, int m) {

        int size = uf.getSize();

        Random random = new Random();

        long startTime = System.nanoTime();

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a, b);
        }

        for (int i = 0; i < m; i++) {
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a, b);
        }

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }


    public static void main(String[] args) {
        int size = 10000000;
        int m = 10000000;

//        UnionFind1 uf1 = new UnionFind1(size);
//        System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
//
//        UnionFind2 uf2 = new UnionFind2(size);
//        System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");

        UnionFind3 uf3 = new UnionFind3(size);
        System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");

        UnionFind4 uf4 = new UnionFind4(size);
        System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");

        UnionFind5 uf5 = new UnionFind5(size);
        System.out.println("UnionFind5 : " + testUF(uf5, m) + " s");
    }
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法与数据结构

数据结构

数据结构

【数据结构】UnionFind 并查集-2 的相关文章

  • 删除分页符时，保持页面格式不乱

    删除分页符时 保持页面格式不乱 1 将光标移到在页面最后 回车 2 选中段落标记后面的 所有 内容 也可以用快捷键ctrl shift end delete 1 将光标移到在页面最后 回车 2 选中段落标记后面的所有内容 也可以用快捷键ct

随机推荐

  • PCIE结构拓扑（RC、EP、SWITCH）介绍

    1 PCIE典型结构拓扑 1 个人理解 红色方框部分一般是在芯片内部集成 对外可提供多个PCIE接口 2 芯片提供的PCIE接口 可以接EP设备 PCI桥 Switch设备 2 RC Root Complex 个人理解 RC在功能上和Swi

  • python 计算置信区间_python 计算数据中值的置信区间

    最近给导师报告处理WISE数据的进展时 对于处理WISE光变导师希望我对每一个观测区间的星等数值给中值的置信度 计算数据的中值95 的置信区间 假设有一组数据如下 data 0 1 2 4 0 1 0 7 1 4 0 9 3 2 0 2 0

  • ApacheBeam：大数据处理的一大神器！

    你知道被认为继MapReduce GFS BigQuery等之后 Google在大数据处理领域对开源社区的又一大贡献是哪个项目吗 答案是ApacheBeam 事实上 Beam 这个项目名称已经很清楚地表明了它的设计初衷 统一批处理 Batc

  • MySQL数据查询 - 联合查询

    联合查询 1 内连接查询 内连接查询 在实际开发中 我们会联合多个表来实现查询 比如把班级表和学生表联合起来就同时可以看到班级 老师和学员的信息 一个班级表 这种只有2张表匹配的行才能显示的连接方式在Mysql 中称之为内连接 INNER

  • 回文词（Uva 401）

    输入一个字符串 判断它是否为回文串以及镜像串 输入字符串保证不含数字0 所谓回文串 就是反转以后与原串相同 如abba和madam 所谓镜像串 就是左右镜像之后和原串相同 如2S和3AIAE 注意 并不是每个字符在镜像之后都能得到一个合法字

  • 以给定值x为基准将单链表分割为两部分，所有小于x的结点都排在大于或等于x的结点之前。

    include LinkList cpp 现单链表的各种基本运算的算法文件单链表的基本运算算法 yyy zxc的博客 CSDN博客 void Split02 LinkNode L ElemType x LinkNode p L gt nex

  • LayUI中的内置模块之 图片/文件上传 layui.upload

    前言 最近在准备找工作的事项 但是作为一个后台也是需要了解一些前端框架的 就目前的来说有大火的VUE 但是VUE还是存在一定的学习成本 所以决定先从对后台友好的LayUI开始入手先做一些小项目练练手 后面会考虑使用VUE ElementUI

  • Tomcat8版本--后台管理弱口令登录

    一 开启vulhub 找到tomcat文件 环境下载并建立 在tomcat8目录下输入以下命令 docker compose build 若出现镜像跳过的问题 直接输入下面的命令 docker compose up d 二 打开网页 第三步

  • MATLAB统计矩阵中非0元素的个数

    A 1 2 0 0 3 3 统计矩阵A中非0元素的个数 sum sum A 0

  • Xml的解析

    文章目录 java的配置文件 dom4j的使用 以下两段代码都有对dom4j的使用 xpath的使用 java的配置文件 在同一个包 从当前包里寻找db properties Demo01 class getResourceAsStream

  • tcpdump: Couldn‘t find user ‘tcpdump‘问题解决

    直接vi etc passwd 加入以下一行 tcpdump x 72 72 sbin nologin 就可以了

  • C++ 移动语义

    C 11 移动语义 首先 移动语义和完美转发这两个概念是在C 的模板编程的基础上 新增的特性 主要是配合模板来使用 本篇会从C 的值类型 到移动拷贝与移动赋值来理解移动语义与完美转发 文章目录 C 11 移动语义 C 的值类型 右值引用与移

  • 51单片机STC15W4K56S4控制步进电机28BYJ-48正反转

    步进电机28BYJ 48 12V 介绍 首先 我们看下步进电机28BYJ 48 12V 外观图 如下 28BYJ 48 12V 含义如下 28表示电机直径28毫米 B表示电机 Y表示永磁 J表示带减速箱 48表示四相八拍 下面解释下 4 相

  • 数组截取--slice（）

    待补充

  • 结构体的定义以及初始化

    一 结构体定义类型 变量的定义 struct是关键字 是结构体类型的标志 在结构体里可以定义相应的成员信息 同时 结构体同样要以分号结尾 struct person char name 20 char sex 20 int age int

  • eclipse 找不到 tomcat 的解决方案

    前言 查了很多教程上配置tomcat时都是直接 File gt gt New gt gt Other gt gt Server gt gt Server gt gt Apache gt gt tomcat 然而我发现在这两个eclipse中

  • 日志大文件拆分

    前言 生产环境没设置好日志文件大小的最大值 导致日志文件过大 普通编辑器根本没法打开 要排查日志改怎么办 拆分日志大文件 如何拆分 split命令专门用来将一个大文件分割成很多个小文件 我把split命令的选项做一个简要说明 选项 含义 b

  • Python opencv库 tkinter 设计屏幕录制工具

    有时 我们在电脑上需要录屏 或制作gif动画 用于演示电脑操作等 如何使用Python来实现 目录 1 使用cv2库生成视频 2 使用tkinter选择录制区域 3 再次实现 4 最终的程序 5 拓展 创建gif动画 1 使用cv2库生成视

  • Docker日志日期时间精确查询

    docker logs since 2020 07 30T10 14 00 until 2020 07 30T10 15 00 tomcat80 这条代码可以通过2个时间来查询指定范围的时间日志 since起始时间 你要从什么时候开始查询

  • 【数据结构】UnionFind 并查集-2

    数据结构源码 UnionFind1 接口 public interface UnionFind int getSize boolean isConnected int p int q void unionElements int p int

热门标签