自学内容网 自学内容网

数据结构之并查集

  • 并查集是一种树型的数据结构
  • 是一种森林,森林中的每棵树表示一个集合,树中的结点对应一个元素

并查集的原理

现在有10个人(从0开始编号),刚开始这10个人互不认识,所以各自属于一个集合。
在这里插入图片描述
并查集会用一个数组来表示这10个人之间的关系,数组的下标对应就是这10个人的编号,刚开始时数组中的元素都初始化为-1。
在这里插入图片描述
数组中的值为负数,即该位置是一颗树的根,且负数的绝对值表示的这棵树(集合)中数据的个数
经过一段时间的相处最终形成了三个朋友圈
在这里插入图片描述

并查集数组中各个位置的值更新
在这里插入图片描述
4号和8号认识了,他们所在的两个集合就需要进行合并,最终变成了两个集合
在这里插入图片描述
合并时,先分别找到这两个元素所在集合的根结点,再将一个集合合并到另一个集合,最后更新数组中根结点的值
在这里插入图片描述

并查集的实现

从上面的分析中,我们可以看出并查集的本质是一个数组,我们对数组内元素不断进行调整,所以我们这样定义并查集

class UnionFind
{
public:
// 刚开始每个人都是独立的,所以刚开始时数组中的元素都初始化为-1
UnionFind(size_t size)
:_ufs(size, -1)
{}

private:
vector<int> _ufs;
};

找根的函数

bool findRoot(int x)
{
int parent = x;
while (parent >= 0)
parent = _ufs[parent];

//路径压缩.提高下次查找效率
while (_ufs[x] >= 0)
{
int tmp = _ufs[x];
_ufs[x] = parent;
x = tmp;
}

return parent;
}

并查集完整代码

#include<iostream>
#include<vector>

using namespace std;

class UnionFind
{
public:
UnionFind(size_t size)
:_ufs(size, -1)
{}

bool findRoot(int x)
{
int parent = x;
while (parent >= 0)
parent = _ufs[parent];

//路径压缩.提高下次查找效率
while (_ufs[x] >= 0)
{
int tmp = _ufs[x];
_ufs[x] = parent;
x = tmp;
}
return parent;
}

void Union(int x1, int x2)
{
int root1 = findRoot(x1);
int root2 = findRoot(x2);
if (root1 != root2)
{
_ufs[root1] += _ufs[root2];
_ufs[root2] = root1;
}
}

bool inSame(int x1, int x2)
{
return findRoot(x1) == findRoot(x2);
}


int size()
{
size_t size = 0;
for (auto x : _ufs)
if (x < 0)
size++;

return size;
}
private:
vector<int> _ufs;
};

原文地址:https://blog.csdn.net/m0_74317866/article/details/142432039

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!