并查集(Union-Find)
并查集(Disjoint Set,也称为Union-Find数据结构)是一种用于高效处理不相交集(即集合内元素互相独立,没有交集)的数据结构。它主要用于解决以下两种操作:
- 查找(Find):确定某个元素所属的集合。
- 合并(Union):将两个不相交的集合并为一个集合。
并查集通常在解决诸如连通性问题、最小生成树算法(如Kruskal算法)和图论中的其他问题时非常有用。
并查集的核心思想
并查集使用树形结构来表示集合,每一个集合对应一棵树,树的根节点作为集合的代表元素。主要操作如下:
- 初始化:每个元素都作为一个单独的集合(即每个元素作为一棵单节点的树)。
- 查找:通过递归或迭代找到元素所在树的根节点,根节点即代表该集合。
- 合并:将两棵树的根节点相连,使得一棵树成为另一棵树的子树。
优化方法
为了提高并查集的性能,通常采用以下两种优化方法:
- 路径压缩(Path Compression):在查找操作中,将查找路径上遇到的所有节点直接连接到根节点,以减少未来的查找时间。
- 按秩合并(Union by Rank):在合并操作中,将秩(树的深度)较小的树连接到秩较大的树的根节点,以保持树的平衡。
核心代码
以下是使用Java实现并查集的基本代码:
class UnionFind {private int[] parent; // 保存每个节点的父节点private int[] rank; // 保存每个节点的秩(树的深度)public UnionFind(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i; // 初始化时每个节点作为自己的父节点rank[i] = 0; // 初始秩为0}}// 查找操作,路径压缩public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路径压缩,直接连接到根节点}return parent[x];}// 合并操作,按秩合并public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX; // 将秩较小的树连接到秩较大的树} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++; // 如果秩相同,合并后秩增加1}}}// 判断两个节点是否在同一个集合中public boolean isConnected(int x, int y) {return find(x) == find(y);}
}
性能特点
经过路径压缩和按秩合并优化的并查集,主要操作的时间复杂度近似为常数时间复杂度,即 O(1):
- 查找(Find):近似 O(1)
- 合并(Union):近似 O(1)
应用场景
并查集在很多算法和问题中都有应用,例如:
- 连通性检测:在图论中,用于快速检测图中的连通分量。
- 最小生成树算法:如Kruskal算法的实现需要高效的集合查找和合并操作。
- 图的遍历:在某些情况下,可以用于快速判断图中两个节点之间是否存在路径。
总结
并查集是一种高效的数据结构,用于处理集合的合并与查找操作,通过路径压缩和按秩合并优化可以使其操作近似于常数时间复杂度。它在解决图论、网络连通性以及其他需要频繁集合操作的问题中具有重要应用价值。
相关文章:
并查集(Union-Find)
并查集(Disjoint Set,也称为Union-Find数据结构)是一种用于高效处理不相交集(即集合内元素互相独立,没有交集)的数据结构。它主要用于解决以下两种操作: 查找(Find)&…...
Linux上的AI框架都有哪些?哪些AI框架适合驱动EACO地球链自动发展完善?
Linux上的AI框架种类繁多,涵盖了深度学习、机器学习、自然语言处理等多个领域。以下是一些常用的AI框架: 深度学习框架 Deeplearning4j 简介:Deeplearning4j(Deep Learning For Java)是Java和Scala环境下的一个开源分…...
java的第一个游戏界面
看视频02_大鱼吃小鱼_添加背景图_尚学堂_哔哩哔哩_bilibili 学习方法: 就对的视频小代码,书籍没有,遇到不懂的问ai 今日成果, 界面代码 package new_gameobj;import java.awt.Graphics; import java.awt.Image; import java.…...

【AIGC】ChatGPT提示词Prompt高效编写模式:Self-ask Prompt、ReACT与Reflexion
博客主页: [小ᶻZ࿆] 本文专栏: AIGC | ChatGPT 文章目录 💯前言💯自我提问 (Self-ask Prompt)如何工作应用实例优势结论 💯协同思考和动作 (ReACT)如何工作应用实例优势结论 💯失败后自我反思 (Reflexion)如何工作…...
android studio无法下载依赖包问题
新建Flutter项目Android项目后,点击运行出现报错! error.png 这是镜像站点无法访问造成的!只需要修改为国内可访问的站点即可。 第一步:修改项目Android目录下的build.gradle buildscript { ext.kotlin_version 1.3.50 repositorie…...

SQL入门
一、SQL 语言概述 数据库就是指数据存储的库,作用就是组织数据并存储数据,数据库如按照:库 -> 表 -> 数据三个层级进行数据组织,而 SQL 语言,就是一种对数据库、数据进行操作、管理、查询的工具,通过…...
Java中的Math类
关于Math类的介绍,这是一个在Java和其他许多编程语言中常见的内置库或模块,主要用于提供各种数学运算的方法。在Java中,Math类位于java.lang包下,它包含大量静态方法执行基本的数学函数,如三角函数、指数函数、对数函数…...

大厂常问iOS面试题–Runloop篇
大厂常问iOS面试题–Runloop篇 一.RunLoop概念 RunLoop顾名思义就是可以一直循环(loop)运行(run)的机制。这种机制通常称为“消息循环机制” NSRunLoop和CFRunLoopRef就是实现“消息循环机制”的对象。其实NSRunLoop本质是由CFRunLoopRef封装的,提供了面向对象的AP…...
【解决】mac报错“zsh: command not found: nvm”
问题描述: 安装nodejs时要先安装nvm,按照网上教程安装之后出现以下异常情况: 1.终端运行npm -v能查到版本,idea运行同样命令提示没找到,像是没安装一样 2.终端关闭重新打开之后,也像是没安装一样,需要重…...

MySQL同步到ES的方案选型
文章目录 1. 同步双写优点缺点实现方式 2. 异步双写优点缺点实现方式 3. 另起应用 SQL 查询写入优点缺点实现方式 4. Binlog 实时同步优点缺点实现方式 5. 应用场景 本文参考: https://www.bilibili.com/video/BV13hvZeaErr/?vd_sourceb7e4d17fd13ffa91c4da6d37c08a6c7c 最近在…...
Transformer 与 CNN的对比
Transformer 相比于 CNN 的优点主要体现在以下几个方面: Transformer 相比 CNN 的优点: 全局依赖建模能力:Transformer 的核心机制是 自注意力机制,它可以直接建模输入序列中任意两个位置之间的依赖关系,无论它们之间的距离有多远。 相比之下,CNN 更擅长处理局部信息,它…...

Maven入门到进阶:构建、依赖与插件管理详解
文章目录 一、Maven介绍1、什么是Maven2、Maven的核心功能 二、Maven核心概念1、坐标GAVP1.1、GroupId1.2、ArtifactId1.3、Version1.3.1、版本号的组成 1.4、Packaging 2、POM、父POM和超级POM2.1、POM (Project Object Model)2.1、父POM(Parent POM)2.…...

炒股VS炒游戏装备,哪个更好做
这个项目,赚个10%都是要被嫌弃的 虽然天天都在抒发自己对股市的看法,但自己自始至终也没有买进任何一支股票。之所以对这个话题感兴趣,着实是因为手上的游戏搬砖项目也是国际性买卖,跟国际形势,国际汇率挂钩࿰…...
AI图像处理工具:开发者高阶用法与最佳实践
引言 随着人工智能技术的迅猛发展,AI图像处理工具正日益成为开发者工作流程中不可或缺的一部分。这些工具不仅能有效处理图像,还能通过深度学习模型实现复杂的图像理解和生成任务。本文将深入探讨开发者在使用AI图像处理工具时的高阶用法,提…...
Spring Boot 2.6=>2.7 升级整理
版本变更: 1、SpringBootTest 属性源优先级:使用 SpringBootTest 注解的测试现在将命令行属性源置于测试属性源之上 在 Spring Boot 2.7 及更高版本中,对 SpringBootTest 的属性源优先级进行了调整,使得通过命令行传递的属性&am…...

Race Track Generator Ultimate:Race Track Generator(赛车场赛道看台场景创建工具)
下载:Unity资源商店链接资源下载链接 效果图:...

数据结构7——二叉树的顺序结构以及堆的实现
在上篇文章数据结构6——树与二叉树中,我们了解了树和二叉树的概念,接着上篇文章,在本篇文章中我们学习二叉树顺序结构的实现。 目录 1. 二叉树的顺序存储结构 2. 堆的概念及结构 1. 堆的概念 2. 堆的结构 3. 堆的实现 1. 堆节点 2. 交…...
leetcode hot100 之【LeetCode 21. 合并两个有序链表】 java实现
LeetCode 21. 合并两个有序链表 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接两个链表的节点组成的。 示例 1: 输入:l1 [1,2,4], l2 [1,3,4] 输出:[1,1,2,3,4,4]示例 2: 输入:l1 …...

Android Camera系列(五):Camera2
Life was like a box of chocolates, you never know what you’re gonna get. 生命就像一盒巧克力,你永远无法知道下一个是什么味道的。 Android Camera系列(一):SurfaceViewCamera Android Camera系列(二࿰…...
从DexMV、VideoDex、MimicPlay到SeeDo:从人类视频中学习:机器人的主流训练方法之一
前言 在此文《UMI——斯坦福刷盘机器人:从手持夹持器到动作预测Diffusion Policy(含代码解读)》的1.1节开头有提到 机器人收集训练数据一般有多种方式,比如来自人类视频的视觉演示 有的工作致力于从视频数据——例如YouTube视频中进行策略学习 即最常见…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

GitFlow 工作模式(详解)
今天再学项目的过程中遇到使用gitflow模式管理代码,因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存,无论是github还是gittee,都是一种基于git去保存代码的形式,这样保存代码…...

DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...

Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...