数据结构(并查集) How did you do it? 怎么做到的!!!

一、前言

并查集的历史

1964年, Bernard A. Galler 和 Michael J. Fischer 首次描述了不相交的并查集,1975 年,Robert Tarjan 是第一个证明O(ma(n))(逆阿克曼函数 (opens new window))算法时间复杂度的上限,并且在 1979 年表明这是受限情况的下限。

2007 年,Sylvain Conchon 和 Jean-Christophe Filliâtre 开发并查集数据结构的半持久版本,并使用证明助手 Coq 将其正确性形式化。 “半持久”意味着结构的先前版本被有效地保留,但访问数据结构的先前版本会使以后的版本无效。它们最快的实现了几乎与非持久算法一样高效的性能且不执行复杂性分析。

#二、并查集数据结构

并查集数据结构(也称为联合-查找数据结构或合并-查找集)基于数组实现的一种跟踪元素的数据结构,这些元素被划分为多个不相交(非重叠)的子集。

它提供了近乎恒定的时间操作(以逆阿克曼函数为界)来添加新集合、合并现有集合以及确定元素是否在同一个集合中。除了推荐算法、好友关系链、族谱等,并查集在 Kruskal (opens new window)的算法中扮演着关键角色,用于寻找无向边加权图的最小生成树。

并查集的定义乍一看有些抽象,也不知道到底在什么场景使用。所以小傅哥给大家举个例子;在以前江湖上有很多门派,各门派见的徒子徒孙碰面难免切磋。为了不让大家打乱套,都要喊一句:”报上名来“ —— 在下叶问,佛山咏春派,师承陈华顺。那么对于这样的场景,我们可以使用并查集给各门派成员合并,方便汇总查询。如图;

  • 张无忌:既然你不是明教,也不是武当的,我就不客气了。
  • 赵敏:不客气你还能咋!我学过咏春!
  • 张无忌:看招!
  • 赵敏:张无忌放开啊,我讨厌你!😒

🤔 但各门派徒子徒孙众多,如果下回遇到赵敏的A丫鬟的Aa丫鬟,没等Aa报家门找族谱完事,也被抠脚了咋办?所以基于这样的情况,要对并查集的各级元素进行优化合并,减少排查路径。

01:粗暴合并02:数量合并03:排序合并04:压缩路径

0→6、6→0 不控制合并数量少合并到数量多排序小合并到排序大排序合并时压缩路径

为了尽可能少的检索次数到根元素,在01:粗暴合并的基础上,有了基于数量、排序的合并方式,同时还包括可以压缩路径。这样再索引到根节点的时间复杂度就又降低了。接下来小傅哥就带着大家看看各个场景的在代码中的操作过程。

#三、并查集结构实现

并查集的实现非常巧妙,只基于数组就可以实现出一个树的效果(基于数组实现的还有二叉堆也是树的结构)。

public class DisjointSet {// 元素public int[] items;// 数量【可选】public int[] count;// 排序【可选】public int[] rank;
}

并查集的元素存放在数组中,通过对数组元素的下标索引指向其他元素,构成一棵树。count 数量、rank 排序,是用于对并查集合并元素时的优化处理。

  • 源码地址:https://github.com/fuzhengwei/java-algorithms(opens new window)
  • 本章源码:https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/disjoint_set(opens new window)
  • 动画演示:https://visualgo.net/zh/ufds?slide=2 (opens new window)—— 并查集结构初次理解还是比较困难的,可以结合学习内容的同时做一些动画演示。

#1. 默认合并 - union(1, 8)

@Override
public int find(int i) {if (i < 0 || i >= items.length) throw new IllegalArgumentException("Index out of range.");return items[i];
}@Override
public void union(int parent, int child) {int parentVal = find(parent);int childVal = find(child);if (parentVal == childVal) return;for (int i = 0; i < items.length; i ++){// 所有值等于原孩子节点对应值的都替换为新的父节点值if (items[i] == childVal){items[i] = parentVal;}}
}

目标:union(1, 8) 将8的根节点合并到1的根节点

  • union 是合并元素的方法,两个入参意思是把 child 指向的根节点,指向 parent 指向的根节点。后面所有案例中 union 方法属性字段意思相同。
  • find 找到元素对应的根节点值,之后使用 union 方法对 items 数组内的元素全部遍历,把所有值等于 child 的节点,都替换为 parent 节点值。
  • 每次合并都for循环比较耗时,所以后续做了一些列的优化。

#2. 粗暴合并 - union(1, 8)

@Override
public int find(int i) {if (i < 0 || i >= items.length)throw new IllegalArgumentException("Index out of range.");// 找到元素的根节点,当i == item[i],就是自己指向自己,这个节点就是根节点while (i != items[i]) {i = items[i];}return i;
}@Override
public void union(int parent, int child) {// 父亲节点的根节点下标值int parentRootIdx = find(parent);// 孩子节点的根节点下标值int childRootIdx = find(child);if (parentRootIdx == childRootIdx) return;// 孩子节点值替换为父节点值items[childRootIdx] = items[parentRootIdx];
}

目标:union(1, 8) 将8的根节点合并到1的根节点

  • find 循环找到置顶节点的最终根节点,例如;8 → 6、6 → 6,那么说明8的根节点是6,因为6自己指向自己了,它就是根节点。
  • union 将 8 指向的根节点 6,更换为 1 指向的根节点 0。最终替换完就是 6 → 0,那么8的根节点有也是0了。
  • 这样虽然减少了每次 for 循环更新,但粗暴的合并会对节点的索引带来一定的复杂度。所以还需要继续优化。

#3. 数量合并 - union(1, 8)

@Override
public int find(int i) {if (i < 0 || i >= items.length)throw new IllegalArgumentException("Index out of range.");// 找到元素的根节点,当i == item[i],就是自己指向自己,这个节点就是根节点while (i != items[i]) {i = items[i];}return i;
}@Override
public void union(int parent, int child) {// 父亲节点的根节点下标值int parentRootIdx = find(parent);// 孩子节点的根节点下标值int childRootIdx = find(child);if (parentRootIdx == childRootIdx) return;if (count[parentRootIdx] >= count[childRootIdx]) {items[childRootIdx] = items[parentRootIdx];count[parentRootIdx] += count[childRootIdx];} else {items[parentRootIdx] = items[childRootIdx];count[childRootIdx] += count[parentRootIdx];}
}

目标:union(1, 8) 将8的根节点合并到1的根节点 & 基于节点的 count 值合并

  • find 循环找到置顶节点的最终根节点,例如;8 → 6、6 → 6,那么说明8的根节点是6,因为6自己指向自己了,它就是根节点。
  • union 在进行元素的根节点合并时,会判断哪个根下的元素少,用少的元素合并到多的元素下。因为这样可以减少多的元素因为处于更低位置所带来的索引耗时。树越深,子叶节点越多,越耗时。

#4. 排序合并 - union(8, 1)

@Override
public int find(int i) {if (i < 0 || i >= items.length)throw new IllegalArgumentException("Index out of range.");// 找到元素的根节点,当i == item[i],就是自己指向自己,这个节点就是根节点while (i != items[i]) {i = items[i];}return i;
}@Override
public void union(int parent, int child) {// 父亲节点的根节点下标值int parentRootIdx = find(parent);// 孩子节点的根节点下标值int childRootIdx = find(child);if (parentRootIdx == childRootIdx)return;if (rank[parentRootIdx] > rank[childRootIdx]) {items[childRootIdx] = items[parentRootIdx];} else if (rank[parentRootIdx] < rank[childRootIdx]) {items[parentRootIdx] = items[childRootIdx];} else {items[childRootIdx] = items[parentRootIdx];rank[parentRootIdx]++;}
}

目标:union(8, 1) 将1的根节点合并到8的根节点(其实效果和union(1,8)是一样的,之所以用union(8, 1)主要体现基于 rank 排序后的合并)& 基于节点的 rank 值合并

  • find 循环找到置顶节点的最终根节点,例如;8 → 6、6 → 6,那么说明8的根节点是6,因为6自己指向自己了,它就是根节点。
  • union 在进行元素的根节点合并时,会判断哪个根的排序小,用少的元素合并到大的根元素下。因为这样可以减少树深大的元素因为处于更低位置所带来的索引耗时。树越深,子叶节点越多,越耗时。
  • 那么此时基于 count、rank 都可以进行优化,不过优化过程中 1→0、0→2 还有2个树高,也可以优化。这就是压缩路径的作用

#5. 压缩路径 - union(8, 1)

@Override
public int find(int i) {if (i < 0 || i >= items.length)throw new IllegalArgumentException("Index out of range.");while (i != items[i]) {// 路径压缩items[i] = items[items[i]];i = items[i];}return i;
}@Override
public void union(int parent, int child) {// 父亲节点的根节点下标值int parentRootIdx = find(parent);// 孩子节点的根节点下标值int childRootIdx = find(child);if (parentRootIdx == childRootIdx)return;if (rank[parentRootIdx] > rank[childRootIdx]) {items[childRootIdx] = items[parentRootIdx];} else if (rank[parentRootIdx] < rank[childRootIdx]) {items[parentRootIdx] = items[childRootIdx];} else {items[childRootIdx] = items[parentRootIdx];rank[parentRootIdx]++;}
}

目标:union(8, 1) 在rank合并下,压缩路径长度。

  • 这里的 union 方法与4. 排序合并相比并没有变化,变化的地方主要在 find 过程中压缩路径。
  • find 基于查找根元素时,对当前元素值对应的父节点值,替换给当前元素。减少一级路径,做到压缩路径的目的。

#四、并查集实现测试

单元测试

@Test
public void test_04() {IDisjointSet disjointSet = new DisjointSet04(9);System.out.println(disjointSet);System.out.println("\n合并元素:\n");disjointSet.union(0, 1);disjointSet.union(2, 3);disjointSet.union(2, 1);disjointSet.union(6, 4);disjointSet.union(6, 5);disjointSet.union(6, 7);disjointSet.union(6, 8);System.out.println(disjointSet);disjointSet.union(8, 1);System.out.println(disjointSet);
}

  • 关于并查集的测试共有6个案例,文中测试举例测试第4个,基于 Rank 优化合并。

测试结果

坐标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
-----------------------------------------
排序 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 
-----------------------------------------
指向 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 合并元素:坐标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
-----------------------------------------
排序 | 2 | 1 | 3 | 1 | 1 | 1 | 2 | 1 | 1 | 
-----------------------------------------
指向 | 2 | 0 | 2 | 2 | 6 | 6 | 6 | 6 | 6 | 坐标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 
-----------------------------------------
排序 | 2 | 1 | 3 | 1 | 1 | 1 | 2 | 1 | 1 | 
-----------------------------------------
指向 | 2 | 0 | 2 | 2 | 6 | 6 | 2 | 6 | 6 | 

  • 经过测试对比图例和控制台输出结果可以看到,(4、5、6、7)→6,6→2,1→0,(0、3)→2,这也是最终树的体现结果。
  • 其他案例源码读者可以测试验证调试,这也可以更好的学习掌握。

#五、常见面试题

  • 并查集叙述?
  • 并查集的使用场景?
  • 并查集怎么合并元素?
  • 并查集合并元素的优化策略?
  • 如何压缩路径?

答 

  1. 并查集是基于数组实现的一种跟踪元素的数据结构,这些元素被划分为多个不相交(非重叠)的子集,是一种用于处理一些不交集(Disjoint Set)的集合的数据结构。
  2.  并查集的使用场景有网络连通性问题,图像处理等等
  3. 并查集通过union方法将两个元素的集合合并成一个集合,对要合并的两个元素找到根节点,然后将其中一个根节点挂在另一个根节点后面
  4. 并查集合并元素的优化策略有默认合并,粗暴合并,数量合并,排序合并,压缩合并
  5. 压缩路径的方式是在 Find 操作过程中,将找到的每个节点直接连接到根节点。这样,下次再查找这些节点时,可以直接找到根节点,大大提高了效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/420984.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C语言深入了解指针一(14)

文章目录 前言一、内存和地址内存究竟该如何理解编址 二、指针变量和地址取地址操作符&解引用操作符*指针变量的大小 总结 前言 终于来到指针啦&#xff01;如前篇末尾总结所说&#xff0c;这是你们马上要下大功夫的地方   但是&#xff0c;就像我们上初中的时候&#xf…

【开发工具】IntelliJ IDEA插件推荐:Json Helper——让JSON处理更高效

导语&#xff1a;在Java开发过程中&#xff0c;JSON作为一种轻量级的数据交换格式&#xff0c;被广泛应用于前后端数据交互。今天&#xff0c;我要为大家介绍一款IntelliJ IDEA插件——Json Helper&#xff0c;帮助开发者更高效地处理JSON数据。 一、什么是Json Helper&#x…

智能优化算法-樽海鞘优化算法(SSA)(附源码)

目录 1.内容介绍 2.部分代码 3.实验结果 4.内容获取 1.内容介绍 樽海鞘优化算法 (Salp Swarm Algorithm, SSA) 虽然名称中提到的是“樽海鞘”&#xff0c;但实际上这个算法是基于群体智能的一种元启发式优化算法&#xff0c;它模拟了樽海鞘&#xff08;Salps&#xff09;在海…

C语言:刷题日志(3)

一.猴子选大王 一群猴子要选新猴王。新猴王的选择方法是&#xff1a;让N只候选猴子围成一圈&#xff0c;从某位置起顺序编号为1~N号。从第1号开始报数&#xff0c;每轮从1报到3&#xff0c;凡报到3的猴子即退出圈子&#xff0c;接着又从紧邻的下一只猴子开始同样的报数。如此不…

阿里云镜像报错 [Errno 14] HTTP Error 302 - Found 问题解决记录

1、问题背景和解决思路 在本地安装 CentOS7 后&#xff0c;网络已调通可正常上网&#xff0c;但切换阿里云镜像后&#xff0c;使用 yum 安装软件时出现 “[Errno 14] HTTPS Error 302 - Found Trying other mirror.” 报错&#xff0c;原因是 yum 源配置问题。给出了详细的解决…

苹果首款AI手机发布!iPhone 16全新AI功能体验感拉满

苹果于2024年秋季盛大发布iPhone 16系列&#xff0c;带来前所未有的AI智能体验。iPhone 16系列不仅硬件全面升级&#xff0c;更融入了尖端的AI技术&#xff0c;为用户带来更加智能化的生活体验。 在科技春晚的舞台上&#xff0c;苹果不负众望地揭开了iPhone 16系列的神秘面纱。…

ubuntu20.04 Qt6引用dcmtk库实现dicom文件读取和字符集转换

1 环境问题 安装完Qt6&#xff0c;新建Qt/QtQuick CMake工程编译出现如下错误: Found package configuration file: Qt6Config.cmake but it set Qt6 FOUND to FALSE so package "Qt6" is considered to be NOT FOUND. 原因&#xff1a; 这是因为系统中缺少OpenG…

缓存穿透、缓存雪崩、缓存击穿

图片没了&#xff0c;真的难受啊。。 缓存穿透 缓存穿透 &#xff1a;缓存穿透是指客户端请求的数据在缓存中和数据库中都不存在&#xff0c;这样缓存永远不会生效&#xff0c;这些请求都会打到数据库。 常见的解决方案有两种&#xff1a; 缓存空对象 优点&#xff1a;实现简单…

Java 入门指南:Java 并发编程 —— 同步工具类 CountDownLatch(倒计时门闩)

文章目录 同步工具类CountDownLatch常用方法使用步骤适用场景使用示例 同步工具类 JUC&#xff08;Java.util.concurrent&#xff09;是 Java 提供的用于并发编程的工具类库&#xff0c;其中包含了一些通信工具类&#xff0c;用于在多个线程之间进行协调和通信&#xff0c;特别…

uniapp媒体

uni.previewImage实现图片放大预览 // 图片预览函数function onPreview(index) {// 收集所有图片的urlvar urls pets.value.data.map(item > item.url)// 预览图片uni.previewImage({current: index, // 当前预览的图片索引urls: urls // 所有图片的url数组})}

大模型api谁家更便宜

1 openai 可点此链接查询价格&#xff1a;https://openai.com/api/pricing/ 2 百度 可点此链接查询价格&#xff1a;https://console.bce.baidu.com/qianfan/chargemanage/list 需要注意&#xff0c;百度千帆平台上还提供其他家的模型调用服务&#xff0c; 如llama, yi-34b等…

秋招突击——算法练习——9/4——73-矩阵置零、54-螺旋矩阵、48-旋转图像、240-搜索二维矩阵II

文章目录 引言复习新作73-矩阵置零个人实现 54-螺旋矩阵个人实现参考实现 48-旋转图像个人实现参考实现 240-搜索二维矩阵II个人实现参考实现 总结 引言 秋招开展的不是很顺利&#xff0c;还是要继续准备&#xff0c;继续刷算法&#xff01;不断完善自己&#xff0c;希望能够找…

yolov5 +gui界面+单目测距 实现对图片视频摄像头的测距

可实现对图片&#xff0c;视频&#xff0c;摄像头的检测 项目概述 本项目旨在实现一个集成了YOLOv5目标检测算法、图形用户界面&#xff08;GUI&#xff09;以及单目测距功能的系统。该系统能够对图片、视频或实时摄像头输入进行目标检测&#xff0c;并估算目标的距离。通过…

揭开Facebook AI的神秘面纱:如何利用人工智能提升社交体验

人工智能&#xff08;AI&#xff09;正迅速成为推动技术进步的核心力量&#xff0c;而Facebook作为全球领先的社交媒体平台&#xff0c;正通过AI技术不断提升用户体验和平台功能。本文将深入探讨Facebook如何利用AI技术&#xff0c;优化社交互动、内容推荐和用户管理&#xff0…

Sentinel 使用案例详细教程

文章目录 一、Sentinel 使用1.1 Sentinel 客户端1.2 Sentinel 控制台1.3 客户端和控制台的通信所需依赖 二、测试 Sentinel 限流规则2.1 启动配置2.2 定义限流资源2.3 配置流量控制规则2.4 运行项目 三、 测试 Sentinel 熔断降级规则3.1 定义资源3.2 配置熔断降级规则3.3 运行项…

info_scan!自动化漏洞扫描系统,附下载链接

在我们团队的日常工作中&#xff0c;定期进行安全演练和漏洞扫描几乎是必不可少的。每次安全互动我们都需要对关键资产进行全面的安全评估&#xff0c;及时发现可能存在的安全隐患。 就在上周&#xff0c;我们针对几个主要服务进行了例行的漏洞扫描。在这个过程中&#xff0c;…

DevOps平台搭建过程详解--Gitlab+Jenkins+Docker+Harbor+K8s集群搭建CICD平台

一、环境说明 1.1CI/CD CI即为持续集成(Continue Integration,简称CI)&#xff0c;用通俗的话讲&#xff0c;就是持续的整合版本库代码编译后制作应用镜像。建立有效的持续集成环境可以减少开发过程中一些不必要的问题、提高代码质量、快速迭代等;(Jenkins) CD即持续交付Con…

合宙低功耗4G模组Air780EX——硬件设计手册01

Air780EX是一款基于移芯EC618平台设计的LTECat1无线通信模组。支持FDD-LTE/TDD-LTE的4G远距离无线 传输技术。另外&#xff0c;模组提供了USB/UART/I2C等通用接口满足IoT行业的各种应用诉求。 一、主要性能 1.1 模块功能框图 1.2 模块型号列表 1.3 模块主要性能 *注: 模组…

Leetcode 最大子数组和

使用“Kadane’s Algorithm”来解决。 Kadane’s Algorithm 在每个步骤中都保持着一个局部最优解&#xff0c;即以当前元素为结尾的最大子数组和(也就是局部最优解)&#xff0c;并通过比较这些局部最优解和当前的全局最优解来找到最终的全局最优解。 Kadane’s Algorithm的核…

巧用工具,Vue 集成 medium-zoom 实现图片缩放

文章目录 巧用工具&#xff0c;Vue 集成 medium-zoom 实现图片缩放介绍medium-zoomVue3集成 medium-zoom 示例Vue2集成 medium-zoom 示例进阶 - 可选参数 巧用工具&#xff0c;Vue 集成 medium-zoom 实现图片缩放 在现代网页开发中&#xff0c;为用户提供良好的视觉体验至关重…