【数据结构】并查集

这篇具有很好参考价值的文章主要介绍了【数据结构】并查集。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

并查集是简单的数据结构,学会并查集,为图打好基础。

并查集的概念

是树状的数据结构,用于处理相交集合的合并与查询

通常用森林表示,一片森林表示一个集合

并查集一般需要完成

  1. 查找元素属于哪个集合
  2. 查看两个元素是否属于同一个集合
  3. 将两个集合归并成一个集合
  4. 集合的个数

并查集的原理  

假设有10个人,用集合表示为{0,1,2,3,4,5,6,7,8,9}

我们用数组表示这十个人

  1. 数组的下标表示人的编号
  2. 数组的内容表示每个人认识其中人的数目 (-1 表示只认识自己)

【数据结构】并查集,数据结构,数据结构,算法,并查集

表示为10片森林

【数据结构】并查集,数据结构,数据结构,算法,并查集

经过一段时间后,他们形成三个小团体,s1{0,6,7,8}  s2{1,4,9} s3{ 2,3,5}

【数据结构】并查集,数据结构,数据结构,算法,并查集

利用并查集表示

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

【数据结构】并查集,数据结构,数据结构,算法,并查集

所以在并查集中,我们会关注数组的下标和数组的内容。

如果数组的内容是负数,那么他就是根(Root)

如果数组的内容为(非负数),那么就指向他的父亲。

所以我们能简单解决这些问题

  • 查找元素属于哪个集合

沿着树形关系一直往上寻找到根(直到找到内容为负数的)

  • 查看元素是否属于同一个集合

寻找到根,不同则表示不是同一个集合

  • 将两个集合归并成一个集合

一个集合归并到另一个集合中,并修改集合的内容

  • 集合的个数

多少个负数内容的位置,就有多少个集合

接下来,来简单实现一个并查集


并查集的模拟

框架

//并查集
class UnionFindSet {
public:
	//构造函数
	UnionFindSet(int n);
    
    //查找元素所在的集合
	int findRoot(int x);

	//合并两个元素所在的集合
	void Union(int x1, int x2)
	
    //获取并查集中集合的个数
	int SetCount();
private:
	vector<int> _set;各个结点之间的关系
};

构造

接收vector容器应该预留的空间

初始化为-1

	UnionFindSet(size_t size)
		:_set(size,-1)
	{}

不需要自定析构函数

默认会调用系统默认析构


查找root

一直向上寻找,变换x ,直到找到内容为负数

	//查找元素是否在集合里
	int FindRoot(int x)
	{
		while (_set[x] >= 0)
		{
			x = _set[x];
		}
		return x;
	}

合并俩个集合

将B合并到A中,A的根内容要改变,B的根内容也要改变

【数据结构】并查集,数据结构,数据结构,算法,并查集

【数据结构】并查集,数据结构,数据结构,算法,并查集

	//合并
	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;	
		}
	}

路径压缩

如果有大量的数据,那么树的层数可能非常高,查找的时候就需要一层一层往上迭代。这时候很浪费效率,这里就提出路径压缩。

路径压缩一般发送在查找根结点,会压缩路径上的所有结点,挂接到根上。

【数据结构】并查集,数据结构,数据结构,算法,并查集

	int FindRoot(int x)
	{
		//找根
		int root = x;
		while (_set[root ] >= 0)
		{
			root = _set[root ];
		}

		//压缩
		while (_set[x] >= 0)
		{
			int parent = _set[x];
			_set[x] = root;

			x = parent;
		}
		return root;

	}

Gitee:提取代码

相关题目

LCR 116. 省份数量

【数据结构】并查集,数据结构,数据结构,算法,并查集

思路:
运用并查集的相关知识

题目给我们一个相邻矩阵,遍历一半矩阵就能知道连通的关系。

我们把矩阵中为1的放到一个集合中,返回集合的数目

解题时,运用lambda表达式,调用找根root的函数。文章来源地址https://www.toymoban.com/news/detail-827951.html

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected[0].size();
        vector<int> _ufs(n,-1);
        //找根 >=0 就往上找
        auto FindRoot=[&_ufs](int x)
        {
            int parent=x;
            while(_ufs[parent]>=0)
            {
                parent=_ufs[parent];
            }
            return parent;
        };

        //遍历,遇到1 并且根不同 就合并 
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(isConnected[i][j]==1)
                {
                    int root1=FindRoot(i);
                    int root2=FindRoot(j);
                    if(root1!=root2)
                    {
                        _ufs[root1]+=_ufs[root2];
                        _ufs[root2]=root1;
                    }
                }
            }
        }

        int count =0;
        for(auto x:_ufs)
        {
            if(x<0)
                count++;
        }
        return count;

    }
};

到了这里,关于【数据结构】并查集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 高阶数据结构 ——— 并查集

    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。 并查集通常用森林来表示,森林中的每棵树表示一个集合,树中的结点对应一个元素。 说明一下: 虽然利用其他数据结构也能完成不相交集合的合并及查询,但在数据量极大的情况下,其耗费的时

    2024年02月03日
    浏览(52)
  • 【数据结构】并查集

    并查集是简单的数据结构,学会并查集,为图打好基础。 是树状的数据结构,用于处理相交集合的合并与查询 通常用森林表示,一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合 查看两个元素是否属于同一个集合 将两个集合归并成一个集合 集合的个数 假

    2024年02月19日
    浏览(35)
  • 【数据结构】--并查集

    目录 一、概念 ​编辑 二、应用场景--“连接”问题(属于同一Qu 三、实现思路  四、如何存储数据 五、定义接口 1.初始化(init) 2.其他 isSame() 六、抽象类 六、Quick Find【v1 所在集合的所有元素都指向 v2 的根节点】 1.Union 1.Union图解 2.注意点:  3.代码实现 2.find  1.find图

    2023年04月09日
    浏览(31)
  • 【高阶数据结构】——并查集

    在一些应用问题中, 需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并 。在此过程中要 反复用到查询某一个元素归属于那个集合的运算 。适合于描述这类问题的抽象数据类型称为 并查集

    2024年02月16日
    浏览(37)
  • 数据结构详细笔记——并查集

    集合:将各个元素划分为若干个互不相交的子集的集合 森林是m(m=0)棵互不相交的树的集合 优化思路:在每次Union操作构建树的时候,尽可能让树不长高 ①用根结点的绝对值表示树的结点的总数 ②Union操作,让小树合并到大树 优化思路:先找到根结点,再将查找路径上所有结

    2024年02月06日
    浏览(38)
  • 数据结构之并查集

    并查表原理是一种 树型的数据结构 ,用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的树根,就能确定它在哪个集合里。这类问题的抽象数据类型称为并查集(uni

    2024年02月12日
    浏览(36)
  • 【数据结构】| 并查集及其优化实现

    以一个直观的问题来引入并查集的概念。 亲戚问题:有一群人,他们属于不同家族,同一个家族里的人互为亲戚,不同家族的人不是亲戚。随机指定两个人,问他们是否有亲戚关系。 以下图3个不相交的集合表示 3 个家族,当询问两个人是否有亲戚关系时,也就是问两个元素

    2024年02月09日
    浏览(37)
  • 计算机基础--->数据结构(9)【并查集】

    并查集是一种用于解决集合合并和查询问题的数据结构,主要用于实现有关集合的操作,它有两种主要操作,合并(union)和查找(find)。 查找(Find):用来确定元素属于哪个集合。它接受一个元素作为参数,并返回这个元素所属集合的代表元素。通过查找操作,可以判断

    2024年02月15日
    浏览(47)
  • 数据结构(八):并查集详解 (多图+动图)

    目录 一、什么是并查集 二、并查集的存储结构 三、并查集的基本操作 (一)初始化 (二)Find操作 (三)Union操作 四、并查集的优化 (一)Union操作优化(小树并入大树) (二)Find操作优化(压缩路径)         并查集的逻辑结构是一个包含N个元素的 集合 ,如图:

    2024年02月03日
    浏览(43)
  • Java高阶数据结构 & 并查集 & 最小生成树

    并查集与最小生成树 1.1 并查集的原理 在一些应用问题中,我们常常会遇到一类问题 一开始是一个人 后来新增的人可能与这个人有关系,也可能与这个人无关系。 一个人与一个人有关系,这个人与另一个人也有关系,那么三人都有关系。 有关系的和没关系的之间是不同的类

    2024年02月03日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包