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

利用Python实现Union-Find算法

Union-Find(又称 并查集)是一种高效解决 动态连通性问题 的算法。它主要提供两种操作:

  1. Union(x, y):将元素 xy 连接。
  2. Find(x):找到元素 x 所属的集合的标识符(通常是集合的根节点)。

常用的优化策略:

  • 路径压缩(Path Compression):Find 操作中,将访问的节点直接连接到根节点,从而加速后续操作。
  • 按秩合并(Union by Rank):Union 操作中,总是将较小的树合并到较大的树中,以减少树的高度。

在这里插入图片描述

1、问题背景

Union-Find 算法又称不交并集算法,是一种用于维护一组元素之间不相交集合的算法。在实际应用中,Union-Find 算法可以用来解决多种问题,例如判断两个元素是否属于同一个集合、将两个集合合并为一个集合等。

在 Union-Find 算法中,每个元素都由一个父节点表示,父节点指向该元素所属的集合的根节点。如果两个元素的父节点相同,则这两个元素属于同一个集合。如果两个元素的父节点不同,则这两个元素不属于同一个集合。

2、解决方案

Python 中 Union-Find 算法有两种实现方法:使用数组和使用字典。

使用数组实现 Union-Find 算法时,每个元素的父节点存储在一个数组中。如果两个元素的父节点相同,则这两个元素属于同一个集合。否则,这两个元素不属于同一个集合。

使用字典实现 Union-Find 算法时,每个元素的父节点存储在一个字典中。字典的键是元素,字典的值是该元素的父节点。如果两个元素的父节点相同,则这两个元素属于同一个集合。否则,这两个元素不属于同一个集合。

下面是使用 Python 实现 Union-Find 算法的示例代码:

def union_find_array(lis):"""使用数组实现 Union-Find 算法。参数:lis: 一组元素。返回:一个列表,其中每个元素的父节点存储在一个数组中。"""# 创建一个数组,将每个元素的父节点初始化为其自身。parents = [i for i in range(len(lis))]def find(x):"""查找元素 x 的父节点。参数:x: 一个元素。返回:元素 x 的父节点。"""# 如果元素 x 的父节点不是其自身,则继续查找元素 x 的父节点。if parents[x] != x:parents[x] = find(parents[x])# 返回元素 x 的父节点。return parents[x]def union(x, y):"""将元素 x 和元素 y 所属的集合合并为一个集合。参数:x: 一个元素。y: 一个元素。"""# 查找元素 x 的父节点。x_parent = find(x)# 查找元素 y 的父节点。y_parent = find(y)# 如果元素 x 和元素 y 所属的集合不是同一个集合,# 则将元素 x 和元素 y 所属的集合合并为一个集合。if x_parent != y_parent:parents[y_parent] = x_parent# 返回父节点数组。return parentsdef union_find_dict(lis):"""使用字典实现 Union-Find 算法。参数:lis: 一组元素。返回:一个字典,其中每个元素的父节点存储在一个字典中。"""# 创建一个字典,将每个元素的父节点初始化为其自身。parents = {i: i for i in lis}def find(x):"""查找元素 x 的父节点。参数:x: 一个元素。返回:元素 x 的父节点。"""# 如果元素 x 的父节点不是其自身,则继续查找元素 x 的父节点。if parents[x] != x:parents[x] = find(parents[x])# 返回元素 x 的父节点。return parents[x]def union(x, y):"""将元素 x 和元素 y 所属的集合合并为一个集合。参数:x: 一个元素。y: 一个元素。"""# 查找元素 x 的父节点。x_parent = find(x)# 查找元素 y 的父节点。y_parent = find(y)# 如果元素 x 和元素 y 所属的集合不是同一个集合,# 则将元素 x 和元素 y 所属的集合合并为一个集合。if x_parent != y_parent:parents[y_parent] = x_parent# 返回父节点字典。return parents# 测试代码。
lis = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]
parents_array = union_find_array(lis)
parents_dict = union_find_dict(lis)
print(parents_array)
print(parents_dict)

上述代码中,union_find_array() 函数和 union_find_dict() 函数分别使用数组和字典实现了 Union-Find 算法。find() 函数和 union() 函数分别是 Union-Find 算法中查找元素父节点和将两个集合合并为一个集合的函数。

使用数组实现 Union-Find 算法的代码如下:

def union_find_array(lis):# 创建一个数组,将每个元素的父节点初始化为其自身。parents = [i for i in range(len(lis))]def find(x):# 如果元素 x 的父节点不是其自身,则继续查找元素 x 的父节点。if parents[x] != x:parents[x] = find(parents[x])# 返回元素 x 的父节点。return parents[x]def union(x, y):# 查找元素 x 的父节点。x_parent = find(x)# 查找元素 y 的父节点。y_parent = find(y)# 如果元素 x 和元素 y 所属的集合不是同一个集合,# 则将元素 x 和元素 y 所属的集合合并为一个集合。if x_parent != y_parent:parents[y_parent] = x_parent# 返回父节点数组。return parents# 测试代码。
lis = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]
parents_array = union_find_array(lis)
print(parents_array)

输出结果为:

[2, 2, 2, 6, 2]

使用字典实现 Union-Find 算法的代码如下:

def union_find_dict(lis):# 创建一个字典,将每个元素的父节点初始化为其自身。parents = {i: i for i in lis}def find(x):# 如果元素 x 的父节点不是其自身,则继续查找元素 x 的父节点。if parents[x] != x:parents[x] = find(parents[x])# 返回元素 x 的父节点。return parents[x]def union(x, y):# 查找元素 x 的父节点。x_parent = find(x)# 查找元素 y 的父节点。y_parent = find(y)# 如果元素 x 和元素 y 所属的集合不是同一个集合,# 则将元素 x 和元素 y 所属的集合合并为一个集合。if x_parent != y_parent:parents[y_parent] = x_parent# 返回父节点字典。return parents# 测试代码。
lis = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]
parents_dict = union_find_dict(lis)
print(parents_dict)

输出结果为:

{1: 2, 2: 2, 3: 2, 4: 6, 5: 6, 6: 6, 7: 2}

基本的 Union-Find 非常适合处理动态连通性问题。优化版本结合路径压缩和按秩合并,使其在实际应用中非常高效。可以扩展实现更多功能,如连通性查询、连通分量计数等。

相关文章:

利用Python实现Union-Find算法

Union-Find(又称 并查集)是一种高效解决 动态连通性问题 的算法。它主要提供两种操作: Union(x, y):将元素 x 和 y 连接。Find(x):找到元素 x 所属的集合的标识符(通常是集合的根节点)。 常用…...

【LeetCode: 912. 排序数组 + 归并排序】

🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,…...

AI时代来了,我们不再需要IDE了

大家好,我是编程乐趣。 最近在思考一个问题,那就是AI这么强大。 未来有没有可能,我们就不需要不需要开发工具了,只需一个浏览器就可以开发软件了。 一、AI带来的变化 1、代码生成与补全 AI工具如GitHub Copilot等能够根据代码…...

PL/SQL语言的网络编程

PL/SQL语言的网络编程 引言 在信息化迅速发展的今天,网络编程作为现代软件开发的重要组成部分,受到了广泛关注。而在数据库管理系统中,Oracle 提供了 PL/SQL(Procedural Language/Structured Query Language)&#x…...

vue video重复视频 设置 srcObject 视频流不占用资源 减少资源浪费

// 直接设置srcObject减少获取视频流:通过 captureStream() 方法从下方视频元素获取视频流。 // 设置 srcObject:将获取到的视频流设置为上方视频的 srcObject 减少资源浪费 // 获取到需要复制到的dom元素 const firstVideoElement proxy.$refs.firs…...

JavaFx 21 项目Markdown 预览、编辑、新建、文件树、删除、重命名

项目文件结构 项目的源代码和资源文件存放在以下路径: 源代码: src/main/java/com/kong/markdown/ 包含多个 Java 文件,主要实现了应用的功能: App.java:主类,可能包含应用的启动逻辑。FileService.java:可能与文件操作相关的服务类。MainController.java:控制器类,可…...

git项目提交步骤(简洁版)

1.创建仓库 2.填写 信息 3.点击这个按钮 4.找到要上传的文件,在目录内右键点击 5.依次执行命令 在命令窗口中输入:git init 复制仓库地址: 在命令窗口中输入:git remote add origin 仓库地址 在命令窗口中输入:…...

风水算命系统架构与功能分析

系统架构 服务端:Java(最低JDK1.8,支持JDK11以及JDK17)数据库:MySQL数据库(标配5.7版本,支持MySQL8)ORM框架:Mybatis(集成通用tk-mapper,支持myb…...

Clojure语言的学习路线

Clojure语言的学习路线 Clojure是一种现代的Lisp方言,运行于Java虚拟机(JVM)上。它具备强大的函数式编程特性,支持并发和多线程编程,适合处理复杂的数据和计算任务。由于其简洁和灵活的语法,Clojure在数据…...

网络安全核心目标CIA

网络安全的核心目标是为关键资产提供机密性(Confidentiality)、可用性(Availablity)、完整性(Integrity)。作为安全基础架构中的主要的安全目标和宗旨,机密性、可用性、完整性频频出现,被简称为CIA,也被成为你AIC,只是顺序不同而已…...

Wi-Fi Direct (P2P)原理及功能介绍

目录 Wi-Fi Direct (P2P)介绍Wi-Fi Direct P2P 概述P2P-GO(P2P Group Owner)工作流程 wifi-Direct使用windows11 wifi-directOpenwrtwifi的concurrent mode Linux环境下的配置工具必联wifi芯片P2P支持REF Wi-Fi Direct &#xff…...

Perl语言的数据结构

Perl语言的数据结构 Perl是一种功能强大的、灵活的脚本语言,广泛用于文本处理、系统管理、网络编程以及许多其他领域。其灵活性不仅体现在语法上,还体现在其丰富的数据结构上。本文将深入探讨Perl的主要数据结构,包括标量、数组、哈希以及引…...

【MFC】设置CTreeCtrl单个节点的文字颜色

问题 功能调整需要依据不同状态设置树控件中单个节点的文字颜色。 分析 1、CTreeCtrl本身有设置文字颜色的接口SetTextColor,但是这个接口是设置树控件整体的文字颜色。 2、在自定义接口可以对树控件单个节点进行更新文字颜色和背景颜色,接收自定义绘制…...

【CSS】设置滚动条样式

文章目录 基本语法用法案例 基本语法 在CSS中,可以使用 ::-webkit-scrollbar 和相关伪元素来为滚动条设置样式,但请注意这些伪元素是非标准的,主要用于WebKit内核浏览器(如Chrome、Safari)。 ::-webkit-scrollbar CSS …...

Gitlab-Runner配置

原理 Gitlab-Runner是一个非常强大的CI/CD工具。它可以帮助我们自动化执行各种任务,如构建、测试和部署等。Gitlab-Runner和Gitlab通过API通信,接收作业并提交到执行队列,Gitlab-Runner从队列中获取作业,并允许在不同环境下进行作…...

代码随想录 哈希 test 8

18. 四数之和 - 力扣(LeetCode) 与三数之和类似,重点在剪枝和去重的区别,由于target可正可负,因此需要分两种情况讨论,如果target为正,则若当前选择的元素之和大于target,需要跳出这…...

[SAP ABAP] 使用LOOP AT...ASSIGNING FIELD-SYMBOL 直接更新内表数据

使用 LOOP AT...ASSIGNING FIELD-SYMBOL... 可以直接修改内表中的数据,而不需要先将内表数据复制到相应的工作区,然后再更新回内表中,从而提高性能 针对上述代码进行优化,我们使用LOOP AT...ASSIGNING FIELD-SYMBOL 直接更新内表数…...

MySQL数据导出导入

一、数据导出 1.导出全库备份到本地的目录 mysqldump -u$USER -p$PASSWD -h127.0.0.1 -P3306 --routines--default-character-setutf8 --lock-all-tables --add-drop-database -A >db.all.sql 2.导出指定库到本地的目录(例如mysql库) mysqldump -u$USER -p$PASSWD -h127.…...

leetcode 127. 单词接龙

题目:127. 单词接龙 - 力扣(LeetCode) 先建立一颗trie树,从beginWord开始bfs;bfs的过程中,对trie树进行dfs寻找“只差一个字母”的其他未遍历到的字符串;直到bfs遍历到endWord。 struct Node …...

如何开发一个支持海量分布式锁的应用库

分布式锁是一种用于控制分布式系统中资源访问的同步机制,确保在任意时刻只有一个客户端能够获取到锁,并对共享资源进行操作。 作用 1.保证数据一致性:在多个节点并发执行的情况下,分布式锁可以防止同时修改同一份数据&#xff0c…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...