当前位置: 首页 > news >正文

并查集(Union-Find)

并查集(Disjoint Set,也称为Union-Find数据结构)是一种用于高效处理不相交集(即集合内元素互相独立,没有交集)的数据结构。它主要用于解决以下两种操作:

  1. 查找(Find):确定某个元素所属的集合。
  2. 合并(Union):将两个不相交的集合并为一个集合。

并查集通常在解决诸如连通性问题、最小生成树算法(如Kruskal算法)和图论中的其他问题时非常有用。

并查集的核心思想

并查集使用树形结构来表示集合,每一个集合对应一棵树,树的根节点作为集合的代表元素。主要操作如下:

  1. 初始化:每个元素都作为一个单独的集合(即每个元素作为一棵单节点的树)。
  2. 查找:通过递归或迭代找到元素所在树的根节点,根节点即代表该集合。
  3. 合并:将两棵树的根节点相连,使得一棵树成为另一棵树的子树。

优化方法

为了提高并查集的性能,通常采用以下两种优化方法:

  1. 路径压缩(Path Compression):在查找操作中,将查找路径上遇到的所有节点直接连接到根节点,以减少未来的查找时间。
  2. 按秩合并(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)

并查集&#xff08;Disjoint Set&#xff0c;也称为Union-Find数据结构&#xff09;是一种用于高效处理不相交集&#xff08;即集合内元素互相独立&#xff0c;没有交集&#xff09;的数据结构。它主要用于解决以下两种操作&#xff1a; 查找&#xff08;Find&#xff09;&…...

Linux上的AI框架都有哪些?哪些AI框架适合驱动EACO地球链自动发展完善?

Linux上的AI框架种类繁多&#xff0c;涵盖了深度学习、机器学习、自然语言处理等多个领域。以下是一些常用的AI框架&#xff1a; 深度学习框架 Deeplearning4j 简介&#xff1a;Deeplearning4j&#xff08;Deep Learning For Java&#xff09;是Java和Scala环境下的一个开源分…...

java的第一个游戏界面

看视频02_大鱼吃小鱼_添加背景图_尚学堂_哔哩哔哩_bilibili 学习方法&#xff1a; 就对的视频小代码&#xff0c;书籍没有&#xff0c;遇到不懂的问ai 今日成果&#xff0c; 界面代码 package new_gameobj;import java.awt.Graphics; import java.awt.Image; import java.…...

【AIGC】ChatGPT提示词Prompt高效编写模式:Self-ask Prompt、ReACT与Reflexion

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | ChatGPT 文章目录 &#x1f4af;前言&#x1f4af;自我提问 (Self-ask Prompt)如何工作应用实例优势结论 &#x1f4af;协同思考和动作 (ReACT)如何工作应用实例优势结论 &#x1f4af;失败后自我反思 (Reflexion)如何工作…...

android studio无法下载依赖包问题

新建Flutter项目Android项目后&#xff0c;点击运行出现报错&#xff01; error.png 这是镜像站点无法访问造成的&#xff01;只需要修改为国内可访问的站点即可。 第一步:修改项目Android目录下的build.gradle buildscript { ext.kotlin_version 1.3.50 repositorie…...

SQL入门

一、SQL 语言概述 数据库就是指数据存储的库&#xff0c;作用就是组织数据并存储数据&#xff0c;数据库如按照&#xff1a;库 -> 表 -> 数据三个层级进行数据组织&#xff0c;而 SQL 语言&#xff0c;就是一种对数据库、数据进行操作、管理、查询的工具&#xff0c;通过…...

Java中的Math类

关于Math类的介绍&#xff0c;这是一个在Java和其他许多编程语言中常见的内置库或模块&#xff0c;主要用于提供各种数学运算的方法。在Java中&#xff0c;Math类位于java.lang包下&#xff0c;它包含大量静态方法执行基本的数学函数&#xff0c;如三角函数、指数函数、对数函数…...

大厂常问iOS面试题–Runloop篇

大厂常问iOS面试题–Runloop篇 一.RunLoop概念 RunLoop顾名思义就是可以一直循环(loop)运行(run)的机制。这种机制通常称为“消息循环机制” NSRunLoop和CFRunLoopRef就是实现“消息循环机制”的对象。其实NSRunLoop本质是由CFRunLoopRef封装的&#xff0c;提供了面向对象的AP…...

【解决】mac报错“zsh: command not found: nvm”

问题描述&#xff1a; 安装nodejs时要先安装nvm,按照网上教程安装之后出现以下异常情况&#xff1a; 1.终端运行npm -v能查到版本&#xff0c;idea运行同样命令提示没找到&#xff0c;像是没安装一样 2.终端关闭重新打开之后&#xff0c;也像是没安装一样&#xff0c;需要重…...

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&#xff08;Parent POM&#xff09;2.…...

炒股VS炒游戏装备,哪个更好做

这个项目&#xff0c;赚个10%都是要被嫌弃的 虽然天天都在抒发自己对股市的看法&#xff0c;但自己自始至终也没有买进任何一支股票。之所以对这个话题感兴趣&#xff0c;着实是因为手上的游戏搬砖项目也是国际性买卖&#xff0c;跟国际形势&#xff0c;国际汇率挂钩&#xff0…...

AI图像处理工具:开发者高阶用法与最佳实践

引言 随着人工智能技术的迅猛发展&#xff0c;AI图像处理工具正日益成为开发者工作流程中不可或缺的一部分。这些工具不仅能有效处理图像&#xff0c;还能通过深度学习模型实现复杂的图像理解和生成任务。本文将深入探讨开发者在使用AI图像处理工具时的高阶用法&#xff0c;提…...

Spring Boot 2.6=>2.7 升级整理

版本变更&#xff1a; 1、SpringBootTest 属性源优先级&#xff1a;使用 SpringBootTest 注解的测试现在将命令行属性源置于测试属性源之上 在 Spring Boot 2.7 及更高版本中&#xff0c;对 SpringBootTest 的属性源优先级进行了调整&#xff0c;使得通过命令行传递的属性&am…...

Race Track Generator Ultimate:Race Track Generator(赛车场赛道看台场景创建工具)

下载&#xff1a;​​Unity资源商店链接资源下载链接 效果图&#xff1a;...

数据结构7——二叉树的顺序结构以及堆的实现

在上篇文章数据结构6——树与二叉树中&#xff0c;我们了解了树和二叉树的概念&#xff0c;接着上篇文章&#xff0c;在本篇文章中我们学习二叉树顺序结构的实现。 目录 1. 二叉树的顺序存储结构 2. 堆的概念及结构 1. 堆的概念 2. 堆的结构 3. 堆的实现 1. 堆节点 2. 交…...

leetcode hot100 之【LeetCode 21. 合并两个有序链表】 java实现

LeetCode 21. 合并两个有序链表 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接两个链表的节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示例 2&#xff1a; 输入&#xff1a;l1 …...

Android Camera系列(五):Camera2

Life was like a box of chocolates, you never know what you’re gonna get. 生命就像一盒巧克力&#xff0c;你永远无法知道下一个是什么味道的。 Android Camera系列&#xff08;一&#xff09;&#xff1a;SurfaceViewCamera Android Camera系列&#xff08;二&#xff0…...

从DexMV、VideoDex、MimicPlay到SeeDo:从人类视频中学习:机器人的主流训练方法之一

前言 在此文《UMI——斯坦福刷盘机器人&#xff1a;从手持夹持器到动作预测Diffusion Policy(含代码解读)》的1.1节开头有提到 机器人收集训练数据一般有多种方式&#xff0c;比如来自人类视频的视觉演示 有的工作致力于从视频数据——例如YouTube视频中进行策略学习 即最常见…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

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

微信小程序之bind和catch

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

Prompt Tuning、P-Tuning、Prefix Tuning的区别

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

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【JavaWeb】Docker项目部署

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

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

基于SpringBoot在线拍卖系统的设计和实现

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