Union-Find(并查集)
洪笳淏 Lv4
 2021-09-15 16:02:00      

并查集介绍

连通性

  对于无向图，对其进行遍历时：

  • 若是连通图，仅需从图中任一顶点出发，就能访问图中的所有顶点。
  • 若是非连通图，需从图中多个顶点出发。每次从一个新顶点出发所访问的顶点集序列恰好是各个连通分量的顶点集。

  比如下面这幅图，总共有 10 个节点，他们互不相连，分别用 0~9 标记：

avatar

  「连通」是一种等价关系，也就是说具有如下三个性质：

  1. 自反性：节点 p 和 p 是连通的。
  2. 对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。
  3. 传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。

函数签名(基本模型)

1
2
3
4
5
6
7
8
func union(p,q int) { // 将p，q节点连接
}

func connected(p,q int) bool { // 判断p，q节点是否连通
}

func countUF(graph *Vertax) int { // 返回途中有多少个连通分量 
}
  • 比如说之前那幅图，0～9 任意两个不同的点都不连通，调用 connected 都会返回 false，连通分量为 10 个。
  • 如果现在调用 union(0, 1)，那么 0 和 1 被连通，连通分量降为 9 个。
  • 再调用 union(1, 2)，这时 0,1,2 都被连通，调用 connected(0, 2) 也会返回 true，连通分量变为 8 个。

avatar

  判断这种「等价关系」非常实用，比如说编译器判断同一个变量的不同引用，比如社交网络中的朋友圈计算等等。

具体实现

  我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。怎么用森林来表示连通性呢？我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。比如说刚才那幅 10 个节点的图，一开始的时候没有相互连通，就是这样：

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type UF struct {
  	count			int		// 记录连通分量
  	parent		[]int	// 节点x的父节点是parent[x]
}

func construct(n int) UF {
  	p := make([]int,n)
  	for i:=0; i<n; i++ {
    	p[i] = i
  	}
  	return UF{
      count : n		// 一开始互不连通
      parent : p	// 父节点指针初始指向自己
  	}
}

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

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func (u UF) union(p,q int) {
  	rootP := u.find(p)
  	rootQ := u.find(q)
  	if rootP == rootQ {
    	return
  	}
  
  	// 将两棵树合为一棵树
  	u.parent[rootP] = rootQ
  	// u.parent[rootQ] = rootP也一样
  	u.count--
}

func (u UF) find(x int) int {
  
  // 根节点的u.parent[x]=x
  	for u.parent[x] != x {
    	x = u.parent[x]
  	}
  	return x
}

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

avatar

1
2
3
4
5
func (u UF) connected(p,q int) bool {
  	rootP := u.find(p)
  	rootQ := u.find(q)
  	return rootP == rootQ
}

  主要 API connected 和 union 中的复杂度都是 find 函数造成的，所以说它们的复杂度和 find 一样。find 主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是 logN，但这并不一定。logN 的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得「树」几乎退化成「链表」，树的高度最坏情况下可能变成 N。所以说上面这种解法，find , union , connected 的时间复杂度都是 O(N)。这个复杂度很不理想的，你想图论解决的都是诸如社交网络这样数据规模巨大的问题，对于 union 和 connected 的调用非常频繁，每次调用需要线性时间完全不可忍受。问题的关键在于，如何想办法避免树的不平衡呢？

平衡性优化

  我们要知道哪种情况下可能出现不平衡现象，关键在于 union 过程：我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，比如下面这种局面：

avatar

  长此以往，树可能生长得很不平衡。我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个 size 数组，记录每棵树包含的节点数，我们不妨称为「重量」：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type UF struct {
  	count			int		// 记录连通分量
  	parent		[]int	// 节点x的父节点是parent[x]
  	size			[]int	// 新增一个数组用于记录树的“重量”,这个数组只对根节点有意义，在使用前需要先判别是否是根节点
}

func construct(n int) UF {
  	p := make([]int,n)
  	s := make([]int,n)
  	for i:=0; i<n; i++ {
    	p[i] = i	// 最初每棵树只有一个节点
      s[i] = 1	// 重量应该初始化为1
  	}
  	return UF{
      count : n		// 一开始互不连通
      parent : p	// 父节点指针初始指向自己
      size : s		// 每个节点的重量应该初始化为1
  	}
}

  比如说 size[3] = 5 表示，以节点 3 为根的那棵树，总共有 5 个节点。这样我们可以修改一下 union 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (u UF) union(p,q int) {
  	rootP := u.find(p)
  	rootQ := u.find(q)
  	if rootP == rootQ {
    	return
  	}
  
  	// 小树接到大树下面，较平衡
  	if u.size[rootP] > u.size[rootQ] {
    		u.parent[rootQ] = rootP
    		u.size[rootP] += u.size[rootQ]
  	} else {
    		u.parent[rootP] = rootQ
    		u.size[rootQ] += u.size[rootP]
  	}
  	u.count--
}

  这样，通过比较树的重量，就可以保证树的生长相对平衡，树的高度大致在 logN 这个数量级，极大提升执行效率。此时，find , union , connected 的时间复杂度都下降为 O(logN)，即便数据规模上亿，所需时间也非常少。

路经压缩

  这步优化特别简单，所以非常巧妙。我们能不能进一步压缩每棵树的高度，使树高始终保持为常数？

avatar

  这样 find 就能以 O(1) 的时间找到某一节点的根节点，相应的，connected 和 union 复杂度都下降为 O(1)。要做到这一点，非常简单，只需要在 find 中加一行代码：

1
2
3
4
5
6
func (u UF) find(x int) int {
  	for u.parent[x] != x {
    	u.parent[x] = u.parent[u.parent[x]]	// 指向爷爷节点 
    	x = u.parent[x]											// 定位到爷爷节点
  	}
}

  这个操作有点匪夷所思，看个 GIF 就明白它的作用了（为清晰起见，这棵树比较极端）：

avatar

  可见，调用 find 函数每次向树根遍历的同时，顺手将树高缩短了，最终所有树高都不会超过 3（union 的时候树高可能达到 3）。PS：读者可能会问，这个 GIF 图的find过程完成之后，树高恰好等于 3 了，但是如果更高的树，压缩后高度依然会大于 3 呀？不能这么想。这个 GIF 的情景是我编出来方便大家理解路径压缩的，但是实际中，每次find都会进行路径压缩，所以树本来就不可能增长到这么高，你的这种担心应该是多余的。

算法模板总结

  先看一下完整代码：

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
type UF struct {
  	count			int
  	parent		[]int
  	size			[]int
}

func construct(n int) UF { // 初始化UF
  	p := make([]int,n)
  	s := make([]int,n)
  	for i:=0; i<n; i++ {
    	p[i] = i
    	size[i] = 1
 		}
  
  	return UF{
      count : n,
      parent : p,
      size : s
  	}
}

func (u UF) find(x int) int {	// 查找两节点是否连通
  	for u.parent[x] != x {
    	u.parent[x] = u.parent[u.parent[x]]
    	x = u.parent[x]
  	}
}

func (u UF) union(p,q int) {	// 使p，q节点连通
  	rootP := u.find(p)
  	rootQ := u.find(q)
  	if rootP == rootQ {
    	return
  	}
  
  	if u.size[rootP] > u.size[rootQ] {
    	u.paremt[rootQ] = rootP
    	u.size[rootP] += u.size[rootQ]
  	} else {
    	u.parent[rootP] = rootQ
    	u.size[rootQ] += u.size[rootP]
  	}
  	u.count--
}

func (u UF) connected(p,q int) bool {	// 查看p，q节点是否连通
  	rootP := u.find(p)
  	rootQ := u.find(q)
  
  	return rootP == rootQ
}

func (u UF) countUF() int {	// 查看连通分量
  	return u.count
}

  Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。

并查集相关题目

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

avatar

1
2
3
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

1
2
输入：board = [["X"]]
输出：[["X"]]

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i] [j]为 ‘X’ 或 ‘O’

解题思路：

  必须是四面被围的 O 才能被换成 X，也就是说边角上的 O 一定不会被围，进一步，与边角上的 O 相连的 O 也不会被 X 围四面，也不会被替换。解决这个问题的传统方法也不困难，先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的 O 换成一个特殊字符，比如 #；然后再遍历整个棋盘，把剩下的 O 换成 X，把 # 恢复成 O。这样就能完成题目的要求，时间复杂度 O(MN)。这个问题也可以用 Union-Find 算法解决。

  你可以把那些不需要被替换的 O 看成一个拥有独门绝技的门派，它们有一个共同祖师爷叫 **dummy**，这些 O 和 dummy 互相连通，而那些需要被替换的 O 与 dummy 不连通。

avatar

  这就是 Union-Find 的核心思路，明白这个图，就很容易看懂代码了。首先要解决的是，根据我们的实现，Union-Find 底层用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘。

  这个很简单，二维坐标 (x,y) 可以转换成 x * n + y 这个数（m 是棋盘的行数，n 是棋盘的列数）。敲黑板，这是将二维坐标映射到一维的常用技巧。

  其次，我们之前描述的「祖师爷」是虚构的，需要给他老人家留个位置。索引 [0.. m*n-1] 都是棋盘内坐标的一维映射，那就让这个虚拟的 dummy 节点占据索引 m * n 好了。

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
type UF struct {
    count   int
    parent  []int
    size    []int
}

func construct(n int) UF { // 初始化UF结构体
    p := make([]int,n)
    s := make([]int,n)
    for i:=0; i<n; i++ {
        p[i] = i
        s[i] = 1
    }

    return UF{
        count:n,
        parent:p,
        size:s,
    }
}

func (u UF) find(x int) int { // 查找根节点的方法
    for u.parent[x] != x {
        u.parent[x] = u.parent[u.parent[x]]
        x = u.parent[x]
    }
    return x
}

func (u UF) union(p,q int) { // 连通两节点的方法
    rootP := u.find(p)
    rootQ := u.find(q)
    if rootP == rootQ {
        return
    }

    if u.size[rootP] > u.size[rootQ] {
        u.parent[rootQ] = rootP
        u.size[rootP] += u.size[rootQ]
    } else {
        u.parent[rootP] = rootQ
        u.size[rootQ] += u.size[rootP]
    }
    u.count--
}

func (u UF) connected(p,q int) bool {  // 查看是否连通的方法
    rootP := u.find(p)
    rootQ := u.find(q)
    return rootP == rootQ
}


func solve(board [][]byte)  { // 函数主题
    m := len(board)
    n := len(board[0])
    u := construct(m*n+1)  // 初始化并查集，多将一位数加入并查集，作为dummy节点（边缘'O'的根节点）

    for i:=0; i<m; i++ { // 将第一列和最后一列的'O'元素与位于m*n处的dummy连通
        if board[i][0] == 'O' {
            u.union(i*n, m*n)
        }
        if board[i][n-1] == 'O' {
            u.union(i*n+(n-1), m*n)
        }
    }

    for j:=1; j<n-1; j++ { // 将第一行和最后一行的'O'元素与位于m*n处的dummy连通
        if board[0][j] == 'O' {
            u.union(j, m*n)
        }
        if board[m-1][j] == 'O' {
            u.union((m-1)*n+j, m*n)
        }
    }

    d := [][]int{{0,1},{1,0},{0,-1},{-1,0}} // 方向数组 d 是上下左右搜索的常用手法
    for i:=1; i<m-1; i++ {
        for j:=1; j<n-1; j++ {
            if board[i][j] == 'O' {
              // 将此 O 与上下左右的 O 连通
                for k:=0; k<4; k++ {
                    x := i+d[k][0]
                    y := j+d[k][1]
                    if board[x][y] == 'O' {
                        u.union(i*n+j, x*n+y)
                    }
                }
            }
        }
    }
		
  	// 所有不和 dummy 连通的 O，都要被替换
    for i:=1; i<m-1; i++ {
        for j:=1; j<n-1; j++ {
            if (!u.connected(i*n+j, m*n)) {
                board[i][j] = 'X'
            }
        }
    }
}
  • Post title：Union-Find(并查集)
  • Post author：洪笳淏
  • Create time：2021-09-15 16:02:00
  • Post link：https://jiahaohong1997.github.io/2021/09/15/Union-Find(并查集)/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments