并查集(Disjiont-set)

清疚 2022-05-24 04:19 138阅读 0赞

# 并查集(Disjiont-set) #

*  并查集(Disjiont-set)
    
     *  简介
     *  算法实现
        
         *  初始化
         *  Find
         *  Union
         *  图示
     *  算法优化
        
         *  加权
         *  启发式合并
         *  路径压缩
         *  小结

> **更新**
> 
>  *  5/23/2018 更新路径压缩代码

## 简介 ##

wiki上关于并查集的[简介][Link 1]

> 在计算机科学中，**并查集**是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个**联合-查找算法**（**union-find algorithm**）定义了两个用于此数据结构的操作：
> 
>  *  Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
>  *  Union：将两个子集合并成同一个集合。

并查集主要用于解决**动态连通性问题**(我也不懂是什么问题).

我们用一个**代表**来标识一个**不交集**. 通常我们不关心哪个成员作为代表, 但是对于属于同一个集合的两个变量, 查询应该得到相同的代表.

举个栗子. 假如有一个大型的计算机网络, 其中有很多台计算机, 如果计算机a与计算机b连通, b与c连通, 那么a与c连通. 对于网络中的两台计算机p, q我们可能有这些操作: 判断p, q是否连通`find(p) == find(q)`; 在p, q之间建立一条路线使两者连通`union(p, q)`.

通过上面的例子不难看出**连通**是一种**等价关系**, 它有以下**性质:**

*  自反性: p与p是连通的
 *  对称性: p与q连通, 则q与p连通
 *  传递性: p与q连通且q与r连通, 则p与r连通

## 算法实现 ##

首先我们用一个数组记录所有元素, 对于`set[i] == k` , `i`表示一个元素, `k`表示元素所属的集合, 通常可以指向或者间接指向集合的**代表**来表示属于这个集合. 当`set[i] == i`是表明`i`是一个**根节点**.

`set[i] ==k`可以理解为`i`, `k`之间有一条连通的路线, 被称为**链接**.

### 初始化 ###

让所有元素指向自己, 表示属于不同的集合, 此时集合中每个元素都是一个**根节点**

const int SIZE = 100001;
    int set[SIZE];
    
    void init(int n) {
        for (int i = 1; i <= n; ++i)
            set[i] = i;
    }

### Find ###

从x向上查找, 直到找到元素的根节点`set[i] == i`, 此根节点就表示这个集合

//循环写法
    int findSet(int x) {
        while (set[x] != x)
            x = set[x]
        return x;
    }
    //递归写法
    int findSet(int x) {
        if (x != set[x])
            find(set[x]);
        else
            return x;
    }

### Union ###

把两个不同的点连起来, 对于`x` ,`y`两个点来说, 相当与把`x`, `y`所在集合合并(传递性), 即x, y所在集合所以元素都**连通**. 所以我们可以找到两个集合的**代表**(根节点), 然后把代表合并即可.

void union_set(int x, int y){
        //分别找到x, y所在集合的代表
        int rootX = find(x);
        int rootY = find(y);
        //如果已经在一个集合中 直接return 不进行合并操作
        if (rootX == rootY) return;//这句此处看起来无关痛痒, 但是在后面的算法优化中很重要
        set[rootX] = rootY;//选取rootY为新集合的代表, 把x所在集合合并到y所在集合
    }

我们在选取谁合并到谁时是随便选取的, 实际上合理的选取能够很好地优化算法.

### 图示 ###

`findSet(6)`即为`set[set[set[set[6]]]] ==1`, `findSet(7)`即为`set[set[7]] == 9`  
![1240][]

`unionSet(6, 7)`

则`rootX = 1, rootY = 9`, 即`set[1] = 9`

![unionSet(6, 7)][unionSet_6_ 7]

## 算法优化 ##

### 加权 ###

上面提到合并是随意选取的, 那么怎么选取可以优化算法呢. 考虑`find`算法的过程, 从低向上查找**代表**, 那么树的高度就决定了`find`的快慢. 所以我们合并时可以考虑把比较矮的树合并到比较高的树上, 这样可以有效降低树的高度, 从而达到优化算法的目的.

这是一种加权并查集, 即每个**代表**会记录该集合的大小(元素多少)作为**代表**的**权**. 合并时我们把权小的代表所在集合(小树)合并到权大的代表所在集合(大树).

启发式合并可以保证对数级别的性能`O(logN)`.

int size[SIZE];//记录对应集合的元素个数 开始时需要初始化为0
    
    void unionSet(int x, int y) {
        int rootX = findSet(x);
        int rootY = findSet(y);
        //这个return特别重要, 如果忽略, 会出现同一个树的大小加倍的错误
        if (rootX == rootY)
            return;
        //比较两个树的大小 小树合并到大树上
        if (size[rootY] > size[rootX]) {
            set[rootX] = rootY;
            size[rootY] += size[rootX];
        } else {
            set[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

加权还有很多其他的用途, 比如统计一个集合的元素个数, 对集合元素分类.

### 启发式合并 ###

和加权的思路一样, 只是记录的是树的高度, 更加直接

int rank[SIZE];//记录树的高度
    
    void unionSet(int x, int y) {
        int rootX = findSet(x);
        int rootY = findSet(y);
        if (rank[rootX] > rank[rootY]) {
            set[rootY] = rootX;
        } else {
            set[rootX] = rootY;
            if (rank[rootY] == rank[rootX])
                rank[rootY]++;
        }
    }

**加权与启发式合并图示**

`unionSet(6, 7)`, 因为`6`所在树比`7`所在树高且大, 所以此时`set[9] = 1`.

可以看到相比没有优化的算法, 这种合并方式有效地降低了树高.

![启发式, 加权合并][1240 1]

### 路径压缩 ###

既然把树高降低能优化算法, 那么我们能在`find`中降低树高吗.

我们可以在`find`中把查找路径上遇到的所有节点都直接**链接**到根节点, 从而实现**路径压缩**, 把树高降低.

代码十分简单, 甚至不比上面的复杂. 时间复杂度非常接近但是没有达到`1`

int findSet(int x) {
        if (set[x] != x)
            return set[x] = findSet(set[x]);//这里最终返回都是根节点
        return x;//一定是根节点返回这句
        //然后根据根节点的返回, 更新查找路径上其他节点
    }
    
    //一种很简洁的写法
    int findSet(int x) {
        return (set[x] == x) ? x : (set[x] = findSet(set[x]));
    }

**路径压缩图示**

![1240][]

`unionSet(6, 7)`(没有优化的合并)

先会调用`findSet(6)`, `findSet(7)`, 查找路径上的所以元素都会直接和根节点**链接**

![findSet(6), findSet(7)][findSet_6_ findSet_7]

之后`set[1] = 9`

![nuion][]

### 小结 ###

*  路径压缩加上启发式合并就是并查集算法的最优解.
 *  一般来说用路径压缩算法就足够了, 可以不再用启发式合并或者加权.(减少代码量)

[Link 1]: https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
[1240]: /images/20220524/1cde0d912a1b4c3d9adb13d095330cc1.png
[unionSet_6_ 7]: /images/20220524/0aff3e8344da44a1aa57c28add950988.png
[1240 1]: /images/20220524/f6335d27e0e941eb94276615791ad3ac.png
[findSet_6_ findSet_7]: /images/20220524/5288fad6f2a0424d9e067a2d48bb1814.png
[nuion]: /images/20220524/e487efc9421e425fa9e100c86e6c710e.png