5.11-5.12Union-Find算法详解

5.11 Union-Find算法详解

5.11.1 问题介绍

并查集算法主要是用来解决图论中**“动态连通性”**问题的。

简单来说动态连通性其实可以抽象成一幅图连线，比如说有一幅图，总共有10个节点，它们互不连通，分别用0-9进行标记

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FcJ1dL6K-1662174261439)(./image/UF-01.png)]

Union-Find算法需要实现以下这两个API

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

• 自反性:p和p是连通的
• 对称性:如果p和q是连通的，那么q和p也是连通的
• 传递性:如果p和q是连通的，q和r是连通的，那么p和r也是连通的

那么在Union-Find算法中，调用union(0,1)，那么0和1就会被连通，连通分量由10个降为9个，再调用union(1,2),连通分量降为8个，对应的:connected(0,2)会返回true,如图所示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6M3jnidW-1662174261440)(./image/UF-02.png)]

5.11.2 基本思路

实现一个并查集的基本思路是:用森林(若干棵树)来表示图的动态连通性，用数组来具体这个森林，其中，森林是我们对于UnionFind的感性认知以及建模，而数组是我们实现这个模型的具体数据结构

怎么用森林来表示连通性呢?我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针就指向自己。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XjMKHhEC-1662174261441)(./image/UF-03.png)]

• 定义数据结构

    //记录连通分量
    private int count;
    //数组定义:节点x的父亲节点是parent[x]
    private int[] parent;

    public UnionFind(int n){
        //一开始各自不连通,那么就各自指向自己
        this.count = n;
        parent = new int[n];
        for(int i = 0;i<n;i++){
            parent[i] = i;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 如果两个节点被连通，则让其中的(任意)一个节点的根节点接到另一个节点的根节点上

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BGTkdwq3-1662174261441)(./image/UF-04.png)]

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //将两棵树合并为一棵
        parent[rootP] = rootQ;
        //只要合并为一个连通图就可以了,这个顺序无所谓
        this.count -- ;
    }
    //判断p和q是否连同
    public boolean isConnected(int p,int q){
        return false;
    }
    //返回图中有几个连通分量
    public int count(){
        return count;
    }

    private int find(int x){//寻找根节点
        //根节点的parent[x] == x
        //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
        //也就是向根节点逼近
        while (x != 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

• 如果节点p和节点q连通的话，它们一定拥有相同的根节点

    //判断p和q是否连同
    public boolean isConnected(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
1
2
3
4
5
6

• 分析时间复杂度，容易知道UnionFind所形成的树可能不是普通的二叉树，对于一般的树可能出现极端不平衡的情况，使得"树"几乎退化成"链表"，树的高度在最坏情况下可能变成N

5.11.3 平衡性优化

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

我们想要知道哪种情况下出现不平衡的情况，其实形成树的过程是关键，因为形成树的过程中，决定了树的结构，来进行代码分析

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //将两棵树合并为一棵
        parent[rootP] = rootQ;
        //只要合并为一个连通图就可以了,这个顺序无所谓
        this.count -- ;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• 这段代码就是简单粗暴地把p所在的树接到q所在的树的节点下面，那么这里就可能出现头重脚轻的不平衡情况，有可能出现两种情况，如下图所示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QIyl3bZp-1662174261442)(./image/UF-05.png)]

我们是希望，小一些的树接到一些树的下面，这样就可以避免头重脚轻，更平衡一些，解决方法是一个备忘录的思想，设立一个size数组，记录每棵树所包含的节点数，我们不妨称为重量

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //小树接到大树下面,比较平衡
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }else{
            parent[rootP] += rootQ;
            size[rootQ] += rootP;
        }
        this.count -- ;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 通过比较树的重量，就可以保证树的生长是相对平衡的，树的高度大致在logN 这个数量级，极大提升执行效率

find、union、connected的时间复杂度都下降为O(logN)，即便数据规模上亿，所需时间也非常少

5.11.4 路径压缩

能否压缩每棵树的高度，使得树的高度始终保持为常数?

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dSfLNonc-1662174261443)(./image/UF-06.png)]

如果形成了这样的结构，这样find就能以O(1)的时间找到某一节点的根节点，相应的connected和union复杂度都下降为O(1)

        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
1
2
3
4

• 要理解这段代码，首先一定要明确parent数组的定义,parent[i]是代表着i编号的节点的上一级节点

parent[x] = parent[parent[x]] ，来做阅读理解:parent[x]是什么?是x的父节点的编号(数字上解析)，是x的父节点的指向关系（关系模型上解析）,=是什么？是改变赋值，让x的父节点修改为什么?修改为x的父节点的父节点，也就是让x节点向上提升了一个层级

然后下一次，让x继续遍历这棵树，让x赋值为其父节点，这样的话就能够得到一棵相对平衡的树

    //记录连通分量
    private int count;
    //数组定义:节点x的父亲节点是parent[x]
    private int[] parent;
    //新增一个数组记录树的重量
    private int[] size;

    public UnionFind(int n){
        //一开始各自不连通,那么就各自指向自己
        this.count = n;
        parent = new int[n];
        for(int i = 0;i<n;i++){
            parent[i] = i;
            size[i] = 1;//树的尺寸一开始都是1
        }
    }

    //将p节点和q节点进行链接
    public void union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ){
            return ;
        }
        //小树接到大树下面,比较平衡
        if(size[rootP] > size[rootQ]){
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }else{
            parent[rootP] = rootQ;
            size[rootQ] += rootP;
        }
        this.count -- ;
    }
    //判断p和q是否连同
    public boolean isConnected(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    //返回图中有几个连通分量
    public int count(){
        return count;
    }

    private int find(int x){//寻找根节点
        //根节点的parent[x] == x
        //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
        //也就是向根节点逼近
        while (x != parent[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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ztZJzvUi-1662174261443)(./image/UF-07.png)]

5.12 Union-Find算法的应用

Union-Find算法解决的是图的动态连通性问题，其关键是能否把原始问题抽象成一个有关图论的问题

算法的关键点如下:

• 用parent数组记录每个节点的父节点，相当于指向父节点的指针，所以parent数组内实际存储着一个森林
• 用size数组记录每棵树的重量，目的是调用union后树依然拥有平衡性，而不会退化成链表，影响操作效率
• 在find函数中进行路径压缩，保证任意树的高度保持在常数，使得union和connectedAPI的时间复杂度为O(1)

5.12.1 DFS的替代方案

输入一个MXN的二维矩阵，其中包含字符X和O，让你找到矩阵中四面被X围住的O，并把它们替换为X

必须是四面被围的O才能被换成X，也就是说边界上的O一定不会被围，进一步，与边角上的O相连的O页不会被X围四面，也不会被替换

这道题的传统方法就是DFS算法，就是直接暴力搜索，其时间复杂度是O(MN)，其中M和N分别为board的长和宽

我们可以用并查集的办法来解决这个问题，我们知道靠边的O不可能被替换,，然后与靠边的O相连的O也不可能被替换，我们可以抽象簇一个dummy节点，然后把这些O抽象成dummy节点的子节点

那么把这些关系抽象成一幅图，运用并查集算法，所有与dummy节点连通的节点是不会被替换的，反之，则是那些需要被替换的

首先要解决的问题是，根据我们的实现,UnionFind底层使用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘

我们可以假设m是棋盘的行数,n是棋盘的列数,那么二维坐标就可以转化成(x*n+y)，这是将二维坐标映射到一维的常用技巧

之前所描述的dummy节点是虚构的，需要给它留一个位置，索引[0...m*n-1]都是棋盘上元素的对应映射，那就让这个虚拟的dummy的节点占据索引m*n即可

    public void solve(char[][] board) {
        if(board.length == 0){
            return;
        }
        int m = board.length;//行数
        int n = board[0].length;//列数
        UnionFind UF = new UnionFind(m*n+1);
        int dummy = m*n;
        //将首列的O与末列的O连通
        for(int i = 0;i<m;i++){
            if(board[i][0] == 'O'){
                UF.union(i*n,dummy);
            }
            if(board[i][n-1] == 'O'){
                UF.union(i*n+n-1,dummy);
            }
        }
        //将首行和末行的O连通
        for(int j = 0;j<n;j++){
            if(board[0][j] == 'O'){
                UF.union(j,dummy);
            }
            if(board[m-1][j] == 'O'){
                UF.union((m-1)*n+j,dummy);
            }
        }
        int[][] steps = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        for (int i = 1;i<m-1;i++){
            for(int j =1;j<n-1;j++){
                if(board[i][j] == 'O'){
                    //将此O与上下左右的O给连通
                    for(int k =0;k<4;k++){
                        int x = i + steps[k][0];
                        int y = i + steps[k][1];
                        if (board[x][y] == 'O'){
                            UF.union(x*n+y,i*n+j);
                        }
                    }
                }
            }
        }
        for(int i = 1;i<m-1;i++){
            for(int j = 1;j<n-1;j++){
                if(!UF.isConnected(dummy,i*n+j)){
                    board[i][j] = 'X';
                }
            }
        }
    }
    class UnionFind {
        //记录连通分量
        private int count;
        //数组定义:节点x的父亲节点是parent[x]
        private int[] parent;
        //新增一个数组记录树的重量
        private int[] size;

        public UnionFind(int n){
            //一开始各自不连通,那么就各自指向自己
            this.count = n;
            parent = new int[n];
            for(int i = 0;i<n;i++){
                parent[i] = i;
                size[i] = 1;//树的尺寸一开始都是1
            }
        }

        //将p节点和q节点进行链接
        public void union(int p,int q){
            int rootP = find(p);
            int rootQ = find(q);
            if(rootP == rootQ){
                return ;
            }
            //小树接到大树下面,比较平衡
            if(size[rootP] > size[rootQ]){
                parent[rootQ] = rootP;
                size[rootP] += size[rootQ];
            }else{
                parent[rootP] += rootQ;
                size[rootQ] += rootP;
            }
            this.count -- ;
        }
        //判断p和q是否连同
        public boolean isConnected(int p,int q){
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }
        //返回图中有几个连通分量
        public int count(){
            return count;
        }

        private int find(int x){//寻找根节点
            //根节点的parent[x] == x
            //这段代码的逻辑:x=parent[x],x赋值为其父节点的值
            //也就是向根节点逼近
            while (x != parent[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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

5.12.2 判断算法等式

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：“a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/satisfiability-of-equality-equations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

• 每个算式equations装着若干字符串表示的算式，每个算式equations[i]都是4，而且只有这两种情况等于或者不等于
• 如果equations中所有的算式都不会冲突，那么返回true，否则返回false
• 动态连通性其实就是一种等价关系，具有自反性、传递性、对称性，其实==也是一种等价关系，具有这些性质，所以这个问题用UF算法就很自然
• 核心思路：将equations中的算式根据和!=分成两部分，先处理等式，使得他们通过相等关系互通，然后处理!=算式，检查不等关系是否破坏关系的连通性

    public boolean equationsPossible(String[] equations) {
        //建立26个字母连通关系
        UnionFind unionFind  = new UnionFind(26);
        for (String equation : equations) {
            if(equation.charAt(1) == '='){
                char x = equation.charAt(0);
                char y = equation.charAt(3);
                unionFind.union(x-'a',y-'a');
            }
        }
        //检查不等关系
        for (String equation : equations) {
            if(equation.charAt(1) == '!'){
                char x = equation.charAt(0);
                char y = equation.charAt(3);
                if(unionFind.isConnected(x-'a',y-'a')){
                    return false;
                }
            }
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

-‘a’);
}
}
//检查不等关系
for (String equation : equations) {
if(equation.charAt(1) == ‘!’){
char x = equation.charAt(0);
char y = equation.charAt(3);
if(unionFind.isConnected(x-‘a’,y-‘a’)){
return false;
}
}
}
return true;
}

1
2
3