算法：并查集_并查集算法

• 在计算机科学中，并查集是一种树形的数据结构，用于处理不交集的合并(union)及查询(find)问题。
• 并查集主要是用来解决动态连通性问题的，比如查询网状图中两个节点的状态，进行数学中集合相关的操作， 如求两个集合的并集等。

其主要操作：

• findRoot：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一个子集
• unionElements：将两个子集合并成同一个集合

啥叫做动态连通性

简单来说，动态连通性可以抽象为一幅图连线。比如下面图中，一共有10个节点，它们互不相连，分别用$09$标记

并查集算法需要实现如下操作：

class UF{
public:
	// 将p和q相连
    void unionElements(int p, int q);
    // 判断p和q是否连通
    bool isConnected(int p, int q);
    // 返回图中有多少个连通分量
    int count();
};
1
2
3
4
5
6
7
8
9
10

这里说的[连通]是一种等价关系，也就是说具有如下三个性质：

• ⾃反性： 节点 p 和 p 是连通的。
• 对称性： 如果节点 p 和 q 连通， 那么 q 和 p 也连通。
• 传递性： 如果节点 p 和 q 连通， q 和 r 连通， 那么 p 和 r 也连通。

如上图：

• 0〜9 任意两个不同的点都不连通， 调⽤ isConnected都会返回 false， 连通分量为 10 个。
• 如果现在调⽤ unionElements(0, 1) ， 那么 0 和 1 被连通， 连通分量降为 9 个。
• 再调⽤ unionElements(1, 2) ， 这时 0,1,2 都被连通， 调⽤ isConnected(0, 2) 也会返回true， 连通分量变为 8 个。

判断这种「等价关系」 ⾮常实⽤， ⽐如说编译器判断同⼀个变量的不同引⽤， ⽐如社交⽹络中的朋友圈计算等等。

而Union-Find 算法的关键就在于 unionElements和 isConnected函数的效率。 那么⽤什么模型来表⽰这幅图的连通状态呢？ ⽤什么数据结构来实现代码呢？

• 一般我们用森林（若⼲棵树） 来表⽰图的动态连通性
• 可以用数组等多种数据结构来模拟实现这个森林

实现

数组实现

怎么实现

怎么用森林来表示连通性呢？我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。刚开始时，图并没有相互连通，如下：

class UnionFind{
private:
    // 记录连通分量
    int cnt;
    // 节点 x 的节点是 parent[x]
    std::vector<int> parent;
public:
    /* 构造函数， n 为图的节点总数 */
    explicit UnionFind(int n){
        // ⼀开始互不连通, ⽗节点指针初始指向⾃⼰
        this->cnt = n;
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    //返回当前的连通分量个数
    int count() const{
        return cnt;
    }


private: 
    // 查找某个节点的父节点
    int findParent(int n){
        return parent[n];
    }

    // 返回某个节点 x 的根节点
    int findRoot(int x){
        // 根节点的 parent[x] == x
        while (parent[x] != x){
            x = parent[x];
        }
        return x;
    }
};
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

如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上

    // 将p和q相连
    void unionElements(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if(rootP == rootQ){
            return;
        }

        // 将两棵树合并为⼀棵
        parent[rootP] = rootQ;
        --cnt;
    }
1
2
3
4
5
6
7
8
9
10
11
12

这样， 如果节点 p 和 q 连通的话， 它们⼀定拥有相同的根节点：

    // 判断p和q是否连通
    bool isConnected(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        return rootQ == rootP;
    }
1
2
3
4
5
6

⾄此， Union-Find 算法就基本完成了。我们来分析下时间复杂度。可以发现，主要API isConnected和 unionElements中的复杂度都是 findRoot函数造成的， 所以说它们的复杂度和 findRoot⼀样。

findRoot主要功能就是从某个节点向上遍历到树根， 其时间复杂度就是树的⾼度。 我们可能习惯性地认为树的⾼度就是 logN ， 但这并不⼀定。 logN 的⾼度只存在于平衡⼆叉树， 对于⼀般的树可能出现极端不平衡的情况， 使得「树」 ⼏乎退化成「链表」 ， 树的⾼度最坏情况下可能变成 N

所以说上⾯这种解法， findRoot, isConnected, unionElements的时间复杂度都是 O(N)。这个复杂度很不理想的， 你想图论解决的都是诸如社交⽹络这样数据规模巨⼤的问题， 对于 unionElements和 isConnected的调⽤⾮常频繁， 每次调⽤需要线性时间完全不可忍受。

问题的关键在于， 如何想办法避免树的不平衡呢？

平衡性优化

我们要知道哪种情况下可能出现不平衡现象，关键在于union过程：

    // 将p和q相连
    void unionElements(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if(rootP == rootQ){
            return;
        }

        // 将两棵树合并为⼀棵
        parent[rootP] = rootQ;
        --cnt;
    }
1
2
3
4
5
6
7
8
9
10
11
12

我们⼀开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下⾯，那么这⾥就可能出现「头重脚轻」 的不平衡状况， ⽐如下⾯这种局⾯：

⻓此以往， 树可能⽣⻓得很不平衡。 我们其实是希望， ⼩⼀些的树接到⼤⼀些的树下⾯， 这样就能避免头重脚轻， 更平衡⼀些。解决⽅法是额外使⽤⼀个 size 数组， 记录每棵树包含的节点数， 我们不妨称为「重量」

private:
    // 记录连通分量
    int cnt;
    // 节点 x 的节点是 parent[x]
    std::vector<int> parent;
    // 新增⼀个数组记录树的“重量”
    std::vector<int> weight;
public:
    /* 构造函数， n 为图的节点总数 */
    explicit UnionFind(int n){
        // ⼀开始互不连通, ⽗节点指针初始指向⾃⼰
        this->cnt = n;
        parent.resize(n);
        weight.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            weight[i] = 1;
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

⽐如说 weight[3] = 5 表⽰， 以节点 3 为根的那棵树， 总共有 5 个节点。 这样我们可以修改⼀下 union ⽅法：

 
    // 将p和q相连
    void unionElements(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if(rootP == rootQ){
            return;
        }

        // ⼩树接到⼤树下⾯， 较平衡
        if(weight[rootP] > weight[rootQ]){
            parent[rootQ] = rootP;
            weight[rootP] += weight[rootQ];
        }else{
            parent[rootP] = rootQ;
            weight[rootQ] += weight[rootP];
        }
        --cnt;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这样， 通过⽐较树的重量， 就可以保证树的⽣⻓相对平衡， 树的⾼度⼤致在 logN 这个数量级， 极⼤提升执⾏效率。

此时， findRoot, isConnected, unionElements 的时间复杂度都下降为 O(logN)， 即便数据规模上亿， 所需时间也⾮常少

路径压缩

这步优化特别简单，所以非常巧妙。我们能不能进一步压缩每棵树的高度，使树高始终保持为常数？这样find就能以 O(1) 的时间找到某一节点的根节点，相应的，isConnected和unionElements 复杂度都下降为 O(1)。

要做到这一点，非常简单，只需要在要做到这一点，非常简单，只需要在find中加一行代码：中加一行代码：

    // 返回某个节点 x 的根节点
    int findRoot(int x){
        // 根节点的 parent[x] == x
        while (parent[x] != x){
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
1
2
3
4
5
6
7
8
9
10

可见，调用find函数每次向树根遍历的同时，顺手将树高缩短了，最终所有树高都不会超过 3（union的时候树高可能达到 3）。

问题：既然有了路径压缩， weight数组的重量平衡还需要吗？ 这个问题很有意思， 因为路径压缩保证了树⾼为常数（不超过 3） ， 那么树就算不平衡， ⾼度也是常数， 基本没什么影响。

论时间复杂度的话，确实，不需要重量也是O(1)。但是如果加上 weight数组辅助， 效率还是略微⾼⼀些， ⽐如下⾯这种情况：

如果带有重量平衡优化， ⼀定会得到情况⼀， ⽽不带重量优化， 可能出现情况⼆。 ⾼度为 3 时才会触发路径压缩那个 while 循环， 所以情况⼀根本不会触发路径压缩， ⽽情况⼆会多执⾏很多次路径压缩， 将第三层节点压缩到第⼆层。

也就是说， 去掉重量平衡， 虽然对于单个的 find 函数调⽤， 时间复杂度依然是 O(1)， 但是对于 API 调⽤的整个过程， 效率会有⼀定的下降。 当然， 好处就是减少了⼀些空间， 不过对于 Big O 表⽰法来说， 时空复杂度都没变。

总结如下：

class UnionFind{
private:
    // 记录连通分量
    int cnt;
    // 节点 x 的节点是 parent[x]
    std::vector<int> parent;
    // 新增⼀个数组记录树的“重量”
    std::vector<int> weight;
public:
    /* 构造函数， n 为图的节点总数 */
    explicit UnionFind(int n){
        // ⼀开始互不连通, ⽗节点指针初始指向⾃⼰
        this->cnt = n;
        parent.resize(n);
        weight.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            weight[i] = 1;
        }
    }

    //返回当前的连通分量个数
    int count() const{
        return cnt;
    }


    // 将p和q相连
    void unionElements(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        if(rootP == rootQ){
            return;
        }

        // ⼩树接到⼤树下⾯， 较平衡
        if(weight[rootP] > weight[rootQ]){
            parent[rootQ] = rootP;
            weight[rootP] += weight[rootQ];
        }else{
            parent[rootP] = rootQ;
            weight[rootQ] += weight[rootP];
        }
        --cnt;
    }

    // 判断p和q是否连通
    bool isConnected(int p, int q){
        int rootP = findRoot(p);
        int rootQ = findRoot(q);
        return rootQ == rootP;
    }

private:
    int findParent(int n){
        return parent[n];
    }

    // 返回某个节点 x 的根节点
    int findRoot(int x){
        // 根节点的 parent[x] == x
        while (parent[x] != x){
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
};

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
66
67
68
69
70

算法的关键点有 3 个：

• ⽤ parent 数组记录每个节点的⽗节点， 相当于指向⽗节点的指针， 所以 parent 数组内实际存储着⼀个森林（若⼲棵多叉树） 。
• ⽤ weight数组记录着每棵树的重量， ⽬的是让unionElements后树依然拥有平衡性， ⽽不会退化成链表， 影响操作效率。
• 在 findRoot函数中进⾏路径压缩， 保证任意树的⾼度保持在常数， 使得unionElements和 isConnected API 时间复杂度为 O(1)。

数组第二种实现（待完成）

我们通过一个数组来实现一个并查集，数组索引作为数据编号：

从上面的图可以知道：

• 0、1、2、3、4属于一个集合，5、6、7、8、9属于一个集合。
• 4 和 5 两个元素就不属于同一个集合(或者不相连)，因为他们对应的编号不一样。4 对应的编号是 2 ，5对应的编号是4
• 如果要合并两个集合(union(1,5))，因为1和 5是属于两个不同的集合
• 合并后，以前分别和元素 1 连接的元素；和 5 连接的元素，也都连接起来了：
  
  根据上面的描述得知，基于上面实现方案的并查集，查询操作的时间复杂度为 O(1)，合并操作的时间复杂度为 O(n)

map实现

class Node{
    int value;
public:
    explicit Node(int v) : value(v){

    }
};

class UnionFind{
   std::map<int, std::shared_ptr<Node>> nodes;
   std::map<std::shared_ptr<Node>, std::shared_ptr<Node>> parents;
   std::map<std::shared_ptr<Node>, int> sizeMap;

public:
    ~UnionFind(){
        for(auto i : nodes){
            
        }
    }
   UnionFind(const std::list<int>& values){
       for(auto v : values){
           auto node = std::make_shared<Node>(v);
           nodes[v] = node;
           parents[node] = node;
           sizeMap[node] = 1;
       }
   }

    // 给你一个节点，请你往上到不能再往上，把代表返回
    std::shared_ptr<Node> findRoot(std::shared_ptr<Node> cur){
        std::stack<std::shared_ptr<Node>> path;
        while (cur != parents[cur]){
            path.emplace(cur);
            cur = parents[cur];
        }
        
        while (!path.empty()){
            parents[path.top()] = cur;
        }
        return cur;
    }
    
    bool  isSameSet(int a, int b){
        return findRoot(nodes[a]) == findRoot(nodes[b]);
    }
    
    void unionEle(int a, int b){
        auto aRoot = findRoot(nodes[a]);
        auto bRoot = findRoot(nodes[b]);
        if(aRoot != bRoot){
            int aSetSize = sizeMap[aRoot];
            int bSetSize = sizeMap[bRoot];
            auto big = aSetSize >= bSetSize ? aRoot : bRoot;
            auto small = big == aRoot ? bRoot : aRoot;
            parents[small] = big;
            sizeMap[big] = aSetSize + bSetSize;
            sizeMap.erase(small);
        }
    }
    
    int sets(){
        return sizeMap.size();
    }
};

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