Disjoint Set 不相交集 相关整理

Posted on | Edited on | In |

在基础数据结构课程中学到的知识，时隔一年之后，真的是忘得一干二净，这些东西，不用，真的就会忘掉。 在思索图像四联通分量标记时等价表的实现时，不知道怎样高效的实现，经人提醒，才发现这就是不相交集/并查集，惭愧。

做一整理，供日后回顾复习。

定义、性质与操作

A disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

操作

Init初始化

给定一些元素，在初始状态，每个都属于不同的集合，初始化的过程就是要体现这一点，这根据实现的不同，会有不同的操作。

Union合并

将两个集合进行合并成为一个集合，即集合中所有的元素有相同的根。

Find查找

找到某个元素的根，目的是确定该元素所属的集合，常用于判断两个元素是否属于一个集合。

实现

数据结构

由于要找到它的根，属于一个集合的元素有相同的根，所以可以想到属于一个集合的元素形成一个树，而整个所有集合就是一个森林。

每一棵树不同于查找树，不会要求从根节点出发找到子节点的元素，只需要给定子节点，找到根，所以每个节点最基本的只需要记录两个值：

  1. 自己所表示的元素
  2. 自己的父元素

这样的信息用数组就可以实现：

数组的下标本身就可以表示自己，数组中存的值可以记录父节点。

关于根节点存储的值

这真的是一个很有趣的问题，子节点存储父节点无疑，但根节点存什么呢？根据自己的需求，可以存相应的值。

1. 0

根节点存0值，表示其是根节点。

2. 本元素

存本元素的值，这样，如果是根节点，则自己与自己所存的值相同，否则为非根节点。

在后续的查找与合并的优化过程中，会用到树的size或height/rank. 所以跟节点会根据需要记录这些值，所以，根节点还可以记录：

3. -size

运用负值，可以区分根节点和非根节点，同时又可以表示树的size，初始化的时候，给每个元素都赋值为-1.

4. -rank/height

类似-size.

操作

实现方式多样，不同的优化方式也有不同的效果。

Naive Solution

没有路径压缩，Naive Union，根节点存0值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void setInit(int size) {
    for (int i = 0; i <= size; ++i) {
        set[i] = 0;
    }
}
void setUnion(int a, int b) {
    set[a] = b;
}
int setFind(int a) {
    if (set[a] == 0)
        return a;
    return setFind(set[a]);
}

Union by size + path compression

根节点初始值为-1，存储-size。
每次查找的时候，都执行路径压缩。
在union的时候，也先进行查找。

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
void setInit(int size) {
    for (int i = 0; i <= size; ++i) {
        set[i] = -1;
    }
}
int setFind(int a) {
    if (set[a] < 0)
        return a;
    return set[a] = setFind(set[a]);
}
void setUnion(int a, int b) {
    int root1 = setFind(a);
    int root2 = setFind(b);
    if (root1 == root2)
        return;
    if (set[root1] <= set[root2]) {
        set[root1] += set[root2];
        set[root2] = root1;
    } else {
        set[root2] += set[root1];
        set[root1] = root2;
    }
}

时间复杂度

结论：带路径压缩，amortized time: O(1)

TODO…看完算法导论有关的那一章再写…

题目

求连通分量，再合适不过了…

LeetCode上有一道四连通分量的题：LeetCode 200. Number of Islands

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
65
class Solution {
    int setFind(int x, vector<int> &set) {
        if (set[x] < 0)
            return x;
        return set[x] = setFind(set[x], set);
    }
    void setUnion(int x, int y, vector<int> &set) {
        int root1 = setFind(x, set);
        int root2 = setFind(y, set);
        if (root1 == root2)
            return;
        if (set[root1] < set[root2]) {
            set[root1] += set[root2];
            set[root2] = root1;
        } else {
            set[root2] += set[root1];
            set[root1] = root2;
        }
    }
    vector<int> setInit(int size) {
        return vector<int>(size, -1);
    }
    int countSet(vector<int> &set) {
        return count_if(set.begin(), set.end(), [](int x) { return x < 0; });
    }
public:
    int numIslands(vector<vector<char>> &grid) {
        if (grid.empty())
            return 0;
        int tagNum = -1;
        vector<vector<int>> tags(grid.size(), vector<int>(grid[0].size(), -1));
        vector<pair<int, int>> equals;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '0')
                    continue;
                if (i - 1 >= 0 && grid[i - 1][j] == '1' && j - 1 >= 0 && grid[i][j - 1] == '1') {
                    tags[i][j] = tags[i][j - 1];
                    if (tags[i][j - 1] != tags[i - 1][j])
                        equals.emplace_back(tags[i][j - 1], tags[i - 1][j]);
                } else if (i - 1 >= 0 && grid[i - 1][j] == '1') {
                    tags[i][j] = tags[i - 1][j];
                } else if (j - 1 >= 0 && grid[i][j - 1] == '1') {
                    tags[i][j] = tags[i][j - 1];
                } else {
                    tagNum++;
                    tags[i][j] = tagNum;
                }
            }
        }
        if (tagNum == -1)
            return 0;
        if (tagNum == 0)
            return 1;
        vector<int> set = setInit(tagNum + 1);
        for (pair<int, int> p : equals) {
            setUnion(p.first, p.second, set);
        }
        return countSet(set);
    }
};

参考

数据结构与算法分析（C语言描述）第二版
https://en.wikipedia.org/wiki/Disjoint-set_data_structure
https://www.jianshu.com/p/def7767982ac
http://blog.csdn.net/dm_vincent/article/details/7655764