欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

详解并查集

程序员文章站 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;
}