【高阶数据结构】并查集 -- 详解

简介: 【高阶数据结构】并查集 -- 详解

一、并查集的原理

1、并查集的本质和概念

(1)本质

并查集的本质:森林。


(2)概念

在一些应用问题中,需要将 n 个不同的元素划分成一些不相交的集合

开始时,每个元素自成一个单元素集合,然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)


比如:某公司今年校招,在全国总共招生 10 人,广州招 4 人,深圳招 3 人,东莞招 3 人,10 个人来自不同的学校,起先互不相识,每个学生都是一个独立的小团体。

现给这些学生进行编号:{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体,数组中的数字代表:该小集体中具有成员的个数。

(初始状态为 -1 ,表示 10 棵树,即每个学生是一个独立的集合)

(跟堆类似,用下标表示关系,双亲表示法)

毕业后,学生们要去公司上班,每个地方的学生自发组织成小分队一起上路,于是:广州学生小分队 s1={0,6,7,8},深圳学生小分队 s2={1,4,9},东莞学生小分队 s3={2,3,5} 就相互认识了,10 个人形成了三个小团体。

假设右三个群主 0, 1, 2 担任队长,负责大家的出行。

一趟火车之旅后,每个小分队成员就互相熟悉,称为了一个朋友圈。

从上图可以看出:

  • 编号 6, 7, 8 同学属于 0 号小分队,该小分队中有 4 人(包含队长 0);
  • 编号为 4和 9 的同学属于 1 号小分队,该小分队有 3 人(包含队长 1);
  • 编号为 3 和 5 的同学属于 2 号小分队,该小分队有 3 个人(包含队长 1)。

仔细观察数组中内融化,可以得出以下结论:

  1. 数组的下标对应集合中元素的编号
  2. 数组中如果为负数负号代表根数字的绝对值代表该集合中元素个数
  3. 数组中如果为非负数,代表该元素双亲在数组中的下标

2、并查集的应用

在公司工作一段时间后,广州小分队中 8 号同学与深圳小分队 1 号同学奇迹般的走到了一起,两个小圈子的学生相互介绍,最后成为了一个小圈子:

现在 0 集合有 7 个人,2 集合有 3 个人,总共两个朋友圈。


通过以上例子可知,并查集一般可以解决一下问题:

(1)查找元素属于哪个集合

沿着数组表示树形关系以上一直找到根(即:树中中元素为负数的位置)。


(2)查看两个元素是否属于同一个集合

沿着数组表示的树形关系往上一直找到树的根,如果根相同表明在同一个集合,否则不在。


(3)将两个集合归并成一个集合

将两个集合中的元素合并将一个集合名称改成另一个集合的名称。


(4)统计集合的个数

遍历数组,数组中元素为负数的个数即为集合的个数。


二、并查集的实现

class UnionFindSet
{
public:
  UnionFindSet(size_t n)
    :_ufs(n, -1)
  {}
 
    // 初始时,将数组中元素全部设置为1
  void Union(int x1, int x2)
  {
    int root1 = FindRoot(x1);
    int root2 = FindRoot(x2);
    // 如果x1已经与x2在同一个集合就不需要合并了
    if (root1 == root2)
      return;
 
    // 控制数据量小的往大的集合合并
    if (abs(_ufs[root1]) < abs(_ufs[root2]))
      swap(root1, root2);
 
    // 将两个集合中元素合并
    _ufs[root1] += _ufs[root2];
        // 将其中一个集合名称改变成另外一个
    _ufs[root2] = root1;
  }
 
    // 给一个元素的编号,找到该元素所在集合的名称
  int FindRoot(int x)
  {
    int root = x;
        // 如果数组中存储的是负数,找到,否则一直继续
    while (_ufs[root] >= 0)
    {
      root = _ufs[root];
    }
 
    //路径压缩
    while (_ufs[x] >= 0)
    {
      int parent = _ufs[x];
      _ufs[x] = root;
      x = parent;
    }
    return root;
  }
 
  bool InSet(int x1, int x2)
  {
    return FindRoot(x1) == FindRoot(x2);
  }
 
    // 数组中负数的个数,即为集合的个数
  size_t SetSize()
  {
    size_t size = 0;
    for (size_t i = 0; i < _ufs.size(); i++)
    {
      if (_ufs[i] < 0)
      {
        size++;
      }
    }
    return size;
  }
 
private:
  vector<int> _ufs;
};


相关文章
|
1月前
|
算法 开发者 计算机视觉
燃爆全场!Python并查集:数据结构界的网红,让你的代码炫酷无比!
在编程的世界里,总有一些数据结构以其独特的魅力和高效的性能脱颖而出,成为众多开发者追捧的“网红”。今天,我们要介绍的这位明星,就是Python中的并查集(Union-Find)——它不仅在解决特定问题上大放异彩,更以其优雅的设计和强大的功能,让你的代码炫酷无比,燃爆全场!
36 0
|
2月前
|
Python
逆天改命!掌握Python并查集,数据结构难题从此不再是你的痛!
在编程旅程中,遇到棘手的数据结构难题是否让你苦恼?别担心,Python并查集(Union-Find)是你的得力助手。这是一种高效处理不相交集合合并及查询的数据结构,广泛应用于网络连通性、社交网络圈子划分等场景。通过维护每个集合的根节点,它实现了快速合并与查询。本文将介绍并查集的基本概念、应用场景以及如何在Python中轻松实现并查集,帮助你轻松应对各种数据结构挑战。
34 3
|
2月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
2月前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
28 0
|
2月前
|
算法 开发者 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
在编程的浩瀚宇宙中,数据结构如同基石,构建了解决问题的坚实框架。而并查集(Union-Find),这位数据结构界的“肌肉男”,以其独特的魅力和强大的功能,让无数开发者在面对复杂关系处理时,都能感受到前所未有的从容与自信。今天,就让我们一同揭开并查集的神秘面纱,看看它是如何成为你编程路上的得力助手的。
31 0
|
2月前
|
算法 程序员 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
并查集,一种处理不相交集合合并与查询的数据结构,被誉为编程的“肌肉男”。它提供Find(找根节点)和Union(合并集合)操作,常用于好友关系判断、图像处理、集合合并等。Python实现中,路径压缩和按秩合并优化效率。并查集的高效性能使其成为解决问题的强大工具,助力程序员应对复杂挑战。
29 0
|
4月前
|
算法 程序员 图形学
脑洞大开!Python并查集:用最简单的方式,解决最复杂的数据结构问题!
【7月更文挑战第17天】并查集,数据结构明星,处理不相交集合合并与查询。Python实现核心操作:查找与合并。路径压缩优化查找,按秩合并保持平衡。实战应用如图连通性判断,算法竞赛利器。掌握并查集,解锁复杂问题简单解法,照亮编程之旅!
52 10
|
4月前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
【7月更文挑战第18天】并查集,数据结构超级英雄,用于不相交集合的合并与查询。Python实现包括初始化、查找根节点和合并操作。应用广泛,如社交网络分析、图论问题、集合划分等。示例代码展示了解决岛屿数量问题,统计连通的“1”单元格数。掌握并查集,提升编程效率,解决复杂问题。
52 6
|
4月前
|
存储 Python
震惊!Python并查集:解锁数据结构新姿势,让你从菜鸟秒变大神!
【7月更文挑战第18天】并查集,一种处理不相交集合的树形数据结构,支持Union(合并)和Find(查询)操作。Python实现中,用字典存储元素及其父节点,初始时每个元素为根。通过路径压缩提高效率。应用包括网络连通性判断、动态连通性检测和集合操作。掌握并查集,提升编程技能,解决复杂问题。开始探索,成为数据结构大师!
42 5
|
4月前
|
Python
逆天改命!掌握Python并查集,数据结构难题从此不再是你的痛!
【7月更文挑战第18天】并查集,一种神器数据结构,用于处理不相交集合合并与查询,解决网络连通性等难题。Python实现常通过记录元素父节点
40 4