算法.图论-并查集上

🕗 发布于 2024-09-20 01:48 算法图论 java

文章目录

1. 并查集介绍

定义：
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。比如说，我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等
并查集的常见的方法:

方法	作用
int find (int)	作用就是查找一个元素所在大集合的代表元素, 返回这个元素
boolean isSameSet (int, int)	判断传入的两个元素是不是同属一个大集合, 返回T/F
void union (int, int)	合并传入的两个元素所代表的大集团(注意不仅仅是这两个元素)

并查集的时间复杂的要求就是实现上述的操作的时间复杂度都是O(1)
下面是关于并查集的一些常见的操作的图示
在这里插入图片描述

2. 并查集的实现

2.1 实现逻辑

不论是哈希表的机构还是list的顺序结构或者是其他的常见的数据结构, 都不可以做到时间复杂度是O(1)的这个指标, 我们直接介绍实现的方式 --> 通过一个father数组以及size数组
关于这两个数组的含义:

数组	含义
father	下标i代表的是元素的编号, father[i]代表的是他的父亲节点
size	下标i代表的是元素的编号, size[i]代表的是这个节点的孩子节点的个数(包括本身)

在这里插入图片描述
初态就是这个样子, 每一个元素的父亲节点都是其本身, 也就是说每一个节点本身就是其所在集合的代表节点, 然后这个集合的大小就是1
下面我们执行操作
step1 : union(a, b)
step2 : union(c, a)
下面是图示(图解一下操作1, 操作2其实是同理的)
在这里插入图片描述
上面的图解也说明了很多问题, 我们的树形结构的挂载的方式是, 小挂大(小的树挂到大树上)
此时进行了union操作之后的逻辑结构就是左下角所示, 此时我们 {a,b} 共属于一个集合, 进行find操作的时候, find(a) 的结果是 b, find(b) 的结果也是 b, 此时size数组中a的值不会再使用了, 因为这时a不可能是领袖节点了, 也就是说这个数据是脏数据…

2.2 isSameSet方法

其实正常来说我们的isSameSet方法和union方法都需要调用find方法, 但是find方法中的路径压缩的技巧是比较重要的, 所以我们单独拎出来放后面说(这里假设已经实现好了), 实现也是比较简单的, 只需要找到这两个元素的代表领袖节点看是不是一个就可以了

//isSameSet方法
    private static boolean isSameSet(int a, int b){
        return find(a) == find(b);
    }

2.3 union方法(小挂大优化)

解释一下小挂大概念, 在算法导论这本书中说到的是一种秩的概念, 本质上也是为了降低树(集团)的高度所做出的努力, 但这个不是特别必要的…, 也就是在两大集团合并的时候, 小集团(小数目的节点)要依附大集团而存在, 也就是合并的时候, 小集团要挂在大集团上面, 这样可以从一定程度上降低树的高度
代码实现如下

//union方法
    private static void union(int a, int b){
        int fa = find(a);
        int fb = find(b);
        if(fa != fb){
            sets--;
            if(size[fa] >= size[fb]){
                father[fb] = fa;
                size[fa] += size[fb];
            }else{
                father[fa] = fb;
                size[fb] += size[fa];
            }
        }
    }

2.4 find方法(路径压缩优化)

上面的union的小挂大优化, 其实不是特别必要的, 但是我们find方法中的路径压缩是一定要完成的, 如果没有路径压缩的话, 我们的时间复杂度的指标就不会是O(1)
路径压缩指的就是, 在find方法找到父亲节点的时候, 同时把我们的沿途所有节点的父亲节点都改为找到的父亲节点, 以便于操作的时候不用遍历一个长链去寻找父亲节点, 图解如下
在这里插入图片描述
假设我们执行find(a)操作, 就会如图所示把我们的沿途的所有节点的父亲节点都改为领袖节点e
我们借助的是stack栈结构, 或者是递归(其实就是系统栈)实现的


    private static final int MAX_CP = 31;

    private static final int[] father = new int[MAX_CP];

    private static final int[] size = new int[MAX_CP];

    private static final int[] stack = new int[MAX_CP];
    
//find方法(路径压缩的迭代实现)
    private static int find1(int a){
        int sz = 0;
        while(father[a] != a){
            stack[sz++] = a;
            a = father[a];
        }

        while(sz > 0){
            father[stack[--sz]] = a;
        }

        return father[a];
    }

//find方法(路径压缩的递归实现)
    private static int find(int a){
        if(father[a] != a){
            father[a] = find(father[a]);
        }
        return father[a];
    }

3. 并查集模板

上面就是我们关于并查集最基本的分析, 我们提供几个测试链接测试一下

牛客并查集模板

//并查集的基本实现方式
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
    private static final int MAXN = 1000001;

    private static final int[] father = new int[MAXN];

    private static final int[] size = new int[MAXN];

    private static final int[] stack = new int[MAXN];

    private static int cnt = 0;

    private static void build(int sz) {
        cnt = sz;
        for (int i = 0; i <= cnt; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    private static int find(int n) {
        //下面就是扁平化(路径压缩的处理技巧)
        int capacity = 0;
        while (father[n] != n) {
            stack[capacity++] = n;
            n = father[n];
        }

        //开始改变沿途节点的指向
        while (capacity > 0) {
            father[stack[--capacity]] = n;
        }
        return father[n];
    }

    private static boolean isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    private static void union(int a, int b) {
        //下面的设计就是小挂大的思想
        int fa = find(a);
        int fb = find(b);
        if (fa != fb) {
            if (size[fa] >= size[fb]) {
                father[fb] = fa;
                size[fa] += size[fb];
            } else {
                father[fa] = fb;
                size[fb] += size[fa];
            }
        }
    }

    //我们使用的是高效率的io工具(使用的其实就是一种缓存的技术)
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            build(n);
            in.nextToken();
            int m = (int)in.nval;
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int op = (int)in.nval;
                in.nextToken();
                int n1 = (int)in.nval;
                in.nextToken();
                int n2 = (int)in.nval;
                if (op == 1) {
                    out.println(isSameSet(n1, n2) ? "Yes" : "No");
                } else {
                    union(n1, n2);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

洛谷并查集模板

//并查集的基本实现方式
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.IOException;

public class Main {
    private static final int MAXN = 100001;

    private static final int[] father = new int[MAXN];

    private static final int[] size = new int[MAXN];

    private static final int[] stack = new int[MAXN];

    private static int cnt = 0;

    private static void build(int sz){
        cnt = sz;
        for(int i = 0; i <= cnt; i++){
            father[i] = i;
            size[i] = 1;
        }
    }

    private static int find(int n){
        //下面就是扁平化(路径压缩的处理技巧)
        int capacity = 0;
        while(father[n] != n){
            stack[capacity++] = n;
            n = father[n];
        }

        //开始改变沿途节点的指向
        while(capacity > 0){
            father[stack[--capacity]] = n;
        }
        return father[n];
    }

    private static boolean isSameSet(int a, int b){
        return find(a) == find(b);
    }

    private static void union(int a, int b){
        //下面的设计就是小挂大的思想
        int fa = find(a);
        int fb = find(b);
        if(fa != fb){
            if(size[fa] >= size[fb]){
                father[fb] = fa;
                size[fa] += size[fb];
            }else{
                father[fa] = fb;
                size[fb] += size[fa];
            }
        }
    }
    
    //我们使用的是高效率的io工具(使用的其实就是一种缓存的技术)
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while(in.nextToken() != StreamTokenizer.TT_EOF){
            int n = (int)in.nval;
            build(n);
            in.nextToken();
            int m = (int)in.nval;
            for(int i = 0; i < m; i++){
                in.nextToken();
                int op = (int)in.nval;
                in.nextToken();
                int n1 = (int)in.nval;
                in.nextToken();
                int n2 = (int)in.nval;
                if(op == 2){
                    out.println(isSameSet(n1, n2) ? "Y" : "N");
                }else{
                    union(n1, n2);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

原文地址：https://blog.csdn.net/2301_81486828/article/details/142370258

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：HBase初探笔记
下一篇：Snowflake怎么用？

Java项目实战II基于Java+Spring Boot+MySQL的共享汽车管理系统(源码+数据库+文档)
在共享经济蓬勃发展的背景下，共享汽车作为一种新型的出行方式，正逐渐改变着人们的出行习惯。然而，随着共享汽车市场规模的不断扩大，车辆管理、用户服务、数据安全等问题日益凸显，传统的管理方式已难以满足当前的
阅读更多2024-11-19
【青牛科技】汽车收音机调频中频放大器——D1145
无线麦克风对讲机。
阅读更多2024-11-19
鸿蒙中位置权限和相机权限
State permissionsMessage: string | Resource = "\"获取当前位置\"需获取定位权限才能正常使用"this.perm
阅读更多2024-11-19
UE5 第一人称射击项目学习（二）
然后，把子弹的向前向量提升（在ue5的标准向量是以1cm为单位，所以虽然子弹跟随视角发射，但是速度太慢），从生成Actor的return Value处拉一根线，获取向前向量乘1000.运行程序，按
阅读更多2024-11-19
【软考】系统架构设计师-数据库设计基础
数据库设计基础知识
阅读更多2024-11-19
MongoDB 监控：确保数据库性能和可靠性
MongoDB 是一个流行的开源 NoSQL 数据库，以其灵活的文档模型和强大的查询语言而闻名。然而，为了确保 MongoDB 的性能和可靠性，监控是至关重要的。本文将讨论 MongoDB 监控的重要
阅读更多2024-11-19
电脑插入U盘，电脑显示新增了，但是双击却显示请将磁盘插入
`CHKDSK 无法供 RAW 驱动器使用` 表明内存卡的文件系统已损坏或丢失，当前处于 **RAW 文件系统** 状态。RAW 表示文件系统无法识别，可能由以下原因导致：
阅读更多2024-11-19
【论文阅读】InstructIR: High-Quality Image Restoration Following Human Instructions
图像恢复是一个基本问题，旨在从退化的图像中恢复出高质量的清晰图像。All-In-One 图像恢复模型能够利用退化特定的信息作为提示，引导恢复模型有效地恢复多种类型和不同程度的退化图像。本研究提出了首个
阅读更多2024-11-19
【Next】字体修改
next/font 包括任何字体文件的内置自动自托管。首先从 next/font/google 导入您想要使用的字体作为函数。（可以按住 ctrl 点进去 google 查看所有字体）然后导入该字体函
阅读更多2024-11-19
Springboot基于GIS的旅游信息管理系统
项目编号：springbootA100基于GIS的旅游信息管理系统是在旅游业迅速发展、旅游需求日益多样化的背景下应运而生的一套综合性信息管理平台，它通过整合旅游资源、提供实时信息、优化服务流程，旨在为
阅读更多2024-11-19