并查集算法中的等级合并和路径压缩

冬明大大_4553

冬明大大_4553

2023-08-29

767人浏览

转载

并查集算法中的等级合并和路径压缩

称为并查集(或不相交集)的算法负责维护不同的集合,并提供操作来验证集合中的成员资格并将集合组合在一起。它熟练地处理并集和查找操作,这对于维护元素之间的当前连接信息至关重要。

语法

为了确保清晰度,让我们首先理解即将在接下来的代码示例中使用的方法的语法。

// Method to perform Union operation
void Union(int x, int y);

// Method to find the representative element of a set
int Find(int x);

算法

并查算法由两个基本操作组成 - 并集和查找。并集运算合并两个集合,查找运算确定集合的代表元素。通过迭代应用并查运算,我们可以构建高效的并查数据结构。

按等级联合

按等级联合技术用于通过确保较小的树始终附加到较大的树的根来优化联合操作。这种方法可以防止树变得过于不平衡,从而导致查找操作效率低下。

按等级联合的算法如下 -

  • 查找包含元素 x 和 y 的集合的代表(根元素)。

  • 如果代表相同,则返回。

  • 如果x的代表的等级大于y的代表的等级,则使y的代表指向x的代表,并更新x的代表的等级。

  • 否则,使 x 的代表指向 y 的代表,并在必要时更新 y 的代表的排名。

路径压缩

路径压缩是另一种优化技术,可降低并查数据结构中树的高度。它的目的是在查找操作期间压平路径,从而为后续操作提供更短的路径。

  • 路径压缩的算法如下 -

  • 查找包含元素 x 的集合的代表(根元素)。

  • 在遍历从x到其代表的路径时,使每个访问过的元素直接指向代表。

    Trae Solo
    Trae Solo

    一款AI开发辅助工具,主要用于字节旗下Trae推出的独立AI编程智能体工具,适合需要提升相关任务效率的用户。

    下载

方法

现在我们已经了解了按等级并集和路径压缩的基本概念,让我们讨论在 C++ 中实现并查算法的两种不同方法。

方法一:基于数组的实现

在这种方法中,我们将每个集合表示为一个数组。每个索引处的值代表元素的父元素。最初,每个元素都是其自己的父元素,表明它是其集合的代表。

算法

  • 让我们开始父数组的初始化过程。每个元素都将被分配其自己的父元素。

  • 使用路径压缩实现查找操作。

  • 使用 Union by Rank 实现 Union 运算。

示例

#include <iostream>
#define MAX_SIZE 100

// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];

void makeSet(int n) {
   for (int i = 0; i  rank[yRoot]) {
      parent[yRoot] = xRoot;
   } else {
      parent[yRoot] = xRoot;
      rank[xRoot]++;
   }
}

int main() {
   // Usage example
   makeSet(10); // Assuming 10 elements in the set
   Union(1, 2);
   Union(3, 4);
    
   // Print parent array
   for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9

方法 2:基于树的实现

为了描述我们研究中的集合,我们使用了基于树的方法。组中的每个项目都与其各自的父节点关联,同时我们指定根节点来表示该特定集合。

算法

  • 初始化父数组,其中每个元素都是其自己的父元素。

  • 使用路径压缩和递归树遍历来实现查找操作。

  • 使用 Union by Rank 实现 Union 运算。

  • 完整的可执行代码

示例

#include <iostream>

#define MAX_SIZE 100

// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];

void makeSet(int n) {
   for (int i = 0; i  rank[yRoot]) {
      parent[yRoot] = xRoot;
   } else {
      parent[yRoot] = xRoot;
      rank[xRoot]++;
   }
}

int main() {
   // Usage example
   makeSet(10); // Assuming 10 elements in the set
   Union(1, 2);
   Union(3, 4);
    
   // Print parent array
   for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Element 0 Parent: 0
Element 1 Parent: 1
Element 2 Parent: 1
Element 3 Parent: 3
Element 4 Parent: 3
Element 5 Parent: 5
Element 6 Parent: 6
Element 7 Parent: 7
Element 8 Parent: 8
Element 9 Parent: 9

结论

总而言之,按等级并集和路径压缩是并查算法中的关键技术。它们分别优化了联合和查找操作,从而提高了性能并实现了高效的连接信息管理。通过在 C++ 中实现这些技术,我们可以有效地解决与集合、连通性和图相关的问题。

总而言之,我们介绍了语法、分步算法,并提供了两个真实的 C++ 可执行代码示例。通过理解和应用按等级并集和路径压缩,您可以增强算法技能并更有效地解决复杂问题。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
c语言union的用法
c语言union的用法

c语言union的用法是一种特殊的数据类型,它允许在相同的内存位置存储不同的数据类型,union的使用可以帮助我们节省内存空间,并且可以方便地在不同的数据类型之间进行转换。使用union时需要注意对应的成员是有效的,并且只能同时访问一个成员。本专题为大家提供union相关的文章、下载、课程内容,供大家免费下载体验。

2023.09.27

869

5

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习