并查集(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视频中进行策略学习 即最常见…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...