详解并查集
程序员文章站
2022-06-22 16:05:46
...
一、概念
并查集主要用来求解不相交集合的问题,主要针对于合并和查找两种算法。
二、并查集实现
并查集的实现主要包含了三个部分:
- 初始化并查集。
- 合并并查集。
- 查找并查集。
(1)并查集的初始化
并查集的初始化是对单个数据建立了一个单独的集合,每个集合应该包含以下两个数据:
- 这个集合所表示的数据。
- 这个集合的根集合所在位置。
由以上两个数据,一般的并查集的结构一般有两种表示形式:
- 结构体构造。
- 数组构造。
①结构体构造
结构体构造如下:
#define MAX 50;
struct Node
{
int date;
int parent;
}node[MAX];
②数组构造
数组构造比较方便简单,因此我们便采用此种方法构造并查集。
(2)合并并查集
合并操作是并查集的关键,我采用如下的图来解释:
①初始化数组
我们开辟一个拥有十个元素的数组,里面所有的数据都存放为-1。
②根据关系更新数组中的数据
假设关系如下:
因此我们需要根据如上关系确定数组中的数据内容,我们把数据0作为根结点,里面存放的是自己的值加上所有子节点内容相加的值,8、9作为子节点,则8、9结点里面存放的内容是父亲结点也就是0号下标(同理,3号结点存放自己结点的值加上5、7结点内容相加的值,5、7结点里面存放的内容是3号结点的下标),如下如所示。
那么如果我们的情况变得复杂呢,关系变为如下图:
那么此时我们的数组就要变为如下所示:
(3)查找并查集
查找并查集是查找并查集的源头结点,因此我们可以采用递归算法,如果数组里面的内容不是指向父节点,则说明到了源头结点,此时返回即可,如果是指向父节点,则去父结点找即可。
三、并查集代码
#include <iostream>
using namespace std;
class UnionSet
{
public:
UnionSet(size_t len)
{
Arr=(int*)malloc(len + 1);
memset(Arr, -1, sizeof(int)*(len+1));
Size = len+1;
}
~UnionSet()
{
free(Arr);
}
void Merge(int x1,int x2)
{
int Root1 = GetRoot(x1);
int Root2 = GetRoot(x2);
if (Root1 != Root2)
{
Arr[Root1] += Arr[Root2];
Arr[Root2] = Root1;
}
}
int GetRoot(int x)
{
int root = x;
while (Arr[root]>=0)
{
root = Arr[root];
}
return root;
}
private:
int * Arr;
size_t Size;
};
int main()
{
const int n = 5;
const int m = 6;
int r[m][2] = { { 1, 2 },{ 2, 3 },{ 4, 5 },{ 1, 3 },{ 5, 4 },{ 3,5 } };
UnionSet set(n);
for (int i = 0; i < m; i++)
{
set.Merge(r[i][0], r[i][1]);
}
return 0;
}
上一篇: 不相交集合的数据结构-并查集