Hexo
0%

7-并查集union-find

发表于

并查集union find/disjoin set

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。用于解决无向图中的环的问题。

(1)结构

定义每个节点的祖先节点是谁

1
vector<int> parent;

(2)初始化

把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。

1
2
3
4
5
6
7
8
9
10
11
union_find(int n)
{
    parent=vector<int>(n);
    init(n);
}

void init(int n)
{
    for (int i=0;i<n;++i)
        parent.at(i)=i;
}

(3)查找

查找元素所在的集合，即根节点(祖先节点)。

1
2
3
4
5
6
int find_root(int i)
{
    while (i!=parent.at(i))
        i=parent.at(i);
    return i;
}

(4)合并

将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。

1
2
3
4
5
6
7
8
9
bool union_vertices(int a,int b)
{
    int a_root=find_root(a);
    int b_root=find_root(b);
    if (a_root==b_root)
        return false;
    parent.at(a_root)=b_root;
    return true;
}

(5)优化

  1. 路径压缩
    每次查找的时候，如果路径较长，需要遍历较长的路径
    实现：则修改信息，以便下次查找的时候速度更快。
    第一步，找到根结点。
    第二步，修改查找路径上的所有节点，将它们都指向根结点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int find_root(int i)
    {
        if (parent.at(i)!=i)
        {
            int root=find_root(parent.at(i));
            parent.at(i)=root;
            return root;
        }
        return i;
    }

  2. 最大秩合并
    两个集合合并时候，两个集合合并可能导致深度进一步增大，导致查找根节点时遍历路径过长。
    实现：就是在对两个不同子集连接时，按照深度来连，也就是深度低的连在深度高的下面。深度高的做父亲节点。
    但是因为会结合路径压缩同时优化，所以rank数组不一定代表的是深度，但也是一个优化的衡量标准。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    vector<int> parent;
    vector<int> rank;
    union_find(int n)
    {
        parent=vector<int>(n);
        rank=vector<int>(n,0);
        init(n);
    }

    void init(int n)
    {
        for (int i=0;i<n;++i)
        {
            parent.at(i)=i;
            rank.at(i)=0;
        }
    }

    bool union_vertices(int a,int b)
    {
        int a_root=find_root(a);
        int b_root=find_root(b);
        if (a_root==b_root)
            return false;
        if (rank.at(a_root)<rank.at(b_root))
            parent.at(a_root)=b_root;
        else
        {
            parent.at(b_root)=a_root;
            if (rank.at(a_root)==rank.at(b_root))
                ++rank.at(a_root);
        }
        return true;
    }

(6)板子

union_find.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#ifndef UNION_FIND
#define UNION_FIND

#include <vector>
using namespace std;

class union_find
{
private:
    vector<int> parent;
    vector<int> rank;
public:
    union_find()
    {
        parent.clear();
        rank.clear();
    }
    
    union_find(int n)
    {
        parent=vector<int>(n);
        rank=vector<int>(n,0);
        init(n);
    }

    void init(int n)
    {
        for (int i=0;i<n;++i)
        {
            parent.at(i)=i;
            rank.at(i)=0;
        }
    }

    int find_root(int i)
    {
        if (parent.at(i)!=i)
        {
            int root=find_root(parent.at(i));
            parent.at(i)=root;
            return root;
        }
        return i;
    }

    bool union_vertices(int a,int b)
    {
        int a_root=find_root(a);
        int b_root=find_root(b);
        if (a_root==b_root)
            return false;
        if (rank.at(a_root)<rank.at(b_root))
            parent.at(a_root)=b_root;
        else
        {
            parent.at(b_root)=a_root;
            if (rank.at(a_root)==rank.at(b_root))
                ++rank.at(a_root);
        }
        return true;
    }
};

#endif