并查集
咕咕咕 fishing

介绍

并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并查询问题。常常在使用中以森林来表示。
哈希表查询很快,但在合并上效率不高。链表合并很快,但查询效率不高。
并查集在合并和查询上都接近 O(1)

两个主要操作:
合并(union):将两个集合合并为一个集合。
查询(find):确定元素属于哪个集合。 并查集中不断往上寻找他的代表元素,用于确定两个元素是否属于同一集合。

原理

并查集是将集合以树形结构进行组合的数据结构,每个元素(节点)都保存着到它代表元素(父节点)的引用。
合并:将两个集合合并,即将一颗树的根连接到另一棵树的根。
查找:根据代表元素找到最顶层的代表元素,相同则在同一集合,否则不在。

这是并查集最基本的表示方式,但它并不是很高效。
因为合并操作过多时,树的深度会加大,可能会导致创建的树严重不平衡。(查询效率会降低)

优化一:按秩合并

按秩(树的深度)合并,即总是将元素少的树连接至元素多的树上
因为影响运行时间的是树的深度,更小的树添加到更深的树的根上将不会增加秩,除非它们的秩相同。

优化二:路径压缩

路径压缩,即在查找代表元素时,将树扁平化(降低深度)。具体操作是将路径上每个元素的代表元素置为最顶层的代表元素(根)
这样树的深度会降低,根节点下只有一层叶子节点。

关于并查集的复杂度(略)

能力不够,证明不出来。
只找到了一篇文章:
借这个问题科普一下并查集各种情况下的时间复杂度
并查集
并查集复杂度

总之,时间复杂度是很低的,接近O(1)。

实现(coding)

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
package UnionFind;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class UnionFind {
// 对样本进行包裹(元素)
public static class Element<V> {
public V value;

public Element(V value) {
this.value = value;
}
}

public static class UnionFindSet<V> {
// 样本与元素的对应
public HashMap<V, Element<V>> elementMap;
// key 某个元素 value 元素的父
public HashMap<Element<V>, Element<V>> fatherMap;
// key 某个集合的代表元素 value 集合的大小
public HashMap<Element<V>, Integer> sizeMap;

/**
* 初始化并查集
*
* @param list
*/
public UnionFindSet(List<V> list) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
// 初始化
for (V value : list) {
// 进行包裹
Element<V> element = new Element<V>(value);
// 样本与元素一一对应
elementMap.put(value, element);
// 父节点(代表元素)都是自己
fatherMap.put(element, element);
// 集合大小都为1(只有本身)
sizeMap.put(element, 1);
}
}

/**
* 查找元素的代表元素
*/
private Element<V> findHead(Element<V> element) {
// 代表元素不是本身时,放入栈中,且一直往上找
Stack<Element<V>> path = new Stack<>();
while (element != fatherMap.get(element)) {
path.push(element);
element = fatherMap.get(element);
}
// 找到代表元素后,将栈中所有子节点的代表元素置为最顶层代表元素
while (!path.isEmpty()) {
fatherMap.put(path.pop(), element);
}
return element;
}

/**
* 判断两样本是否在同一集合
*/
public boolean isSameSet(V a, V b) {
// 并查集中是否有该元素(是否初始化)
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
// 代表元素是否相同
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}

/**
* 合并集合
*/
public void union(V a, V b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
// 获取对应元素
Element<V> aFather = findHead(elementMap.get(a));
Element<V> bFather = findHead(elementMap.get(b));
// 不在同一集合时,将节点少的集合添加到节点多的集合中
if (aFather != bFather) {
Element<V> big = sizeMap.get(aFather) >= sizeMap.get(bFather) ? aFather : bFather;
Element<V> small = big == aFather ? bFather : aFather;
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(aFather) + sizeMap.get(bFather));
sizeMap.remove(small);
}
}
}
}

}

应用

岛问题
【题目】
一个矩阵中只有0和1两种值,每个位置都可以和自己的上、下、左、右四个位置相连,如
果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有多少个岛?
【举例】
001010
111010
100100
000000
这个矩阵中有三个岛
【进阶】
如何设计一个并行算法解决这个问题

  1. 使用递归暴力求解
  2. 将矩阵进行划分,然后每块都使用递归求解,最后进行合并(这里只分成了两块,使用两个线程模拟)

实现:

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
package UnionFind;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CountDownLatch;

public class Application {
/**
* 数组封装后的对象
*/
private static class Node {
int i;
int j;
int value;

public Node(int i, int j, int value) {
this.i = i;
this.j = j;
this.value = value;
}
}

private static Node[][] nodes;
private static UnionFind.UnionFindSet<Node> unionFindSet;

/**
* 第二种解法
* 也是递归感染,但是是并行的。将矩阵进行划分,然后分别统计,最后将结果合并。
*/
public static int countIslandsUnionFind(int[][] m) throws InterruptedException {
if (m == null || m[0] == null) {
return 0;
}
// 获取矩阵大小
int N = m.length;
int M = m[0].length;
// 设置返回值数组,供两个线程使用
final int[] results = {0, 0};
// 将数组的元素封装成对象,并将岛加入列表,放入并查集
List<Node> list = new ArrayList<>();
nodes = new Node[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
Node node = new Node(i, j, m[i][j]);
nodes[i][j] = node;
if (m[i][j] == 1) {
list.add(node);
}
}
}
// 初始化并查集
unionFindSet = new UnionFind.UnionFindSet<Node>(list);
// 开启两个线程,分别统计一半
final CountDownLatch latch = new CountDownLatch(2);
Thread t1 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M / 2; j++) {
if (nodes[i][j].value == 1) {
results[0]++;
infectUnionFind(i, j, 0, N, 0, M / 2);
}
}
}
latch.countDown();
}
});
Thread t2 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < N; i++) {
for (int j = M / 2; j < M; j++) {
if (nodes[i][j].value == 1) {
results[1]++;
infectUnionFind(i, j, 0, N, M / 2, M);
}
}
}
latch.countDown();
}
});
t1.start();
t2.start();
latch.await();
// 合并,判断分界线两侧的元素是否是相连的岛
int result = results[0] + results[1];
for (int i = 0; i < N; i++) {
if (nodes[i][M / 2 - 1].value == nodes[i][M / 2].value && nodes[i][M / 2 - 1].value == 2 && !unionFindSet.isSameSet(nodes[i][M / 2 - 1], nodes[i][M / 2])) {
unionFindSet.union(nodes[i][M / 2 - 1], nodes[i][M / 2]);
result--;
}
}
return result;
}

/**
* 感染过程
*/
private static boolean infectUnionFind(int i, int j, int N1, int N2, int M1, int M2) {
if (i < N1 || i >= N2 || j < M1 || j >= M2 || nodes[i][j].value != 1) {
return false;
}
// i,j没有越界且当前位置为1
nodes[i][j].value = 2;
// 感染上下左右四个位置
if (infectUnionFind(i + 1, j, N1, N2, M1, M2)) {
unionFindSet.union(nodes[i][j], nodes[i + 1][j]);
}
if (infectUnionFind(i - 1, j, N1, N2, M1, M2)) {
unionFindSet.union(nodes[i][j], nodes[i - 1][j]);
}
if (infectUnionFind(i, j + 1, N1, N2, M1, M2)) {
unionFindSet.union(nodes[i][j], nodes[i][j + 1]);
}
if (infectUnionFind(i, j - 1, N1, N2, M1, M2)) {
unionFindSet.union(nodes[i][j], nodes[i][j - 1]);
}
return true;
}

/**
* 第一种解法
* 递归感染
* 时间复杂度 O(N*M)
*/
public static int countIslands(int[][] m) {
if (m == null || m[0] == null) {
return 0;
}
// 获取矩阵大小
int N = m.length;
int M = m[0].length;
int result = 0;
// 遍历矩阵中每个元素
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 是岛则进行感染过程
if (m[i][j] == 1) {
result++;
infect(m, i, j, N, M);
}
}
}
return result;
}

/**
* 递归传染
*/
private static void infect(int[][] m, int i, int j, int N, int M) {
if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {
return;
}
// i,j没有越界且当前位置为1
m[i][j] = 2;
// 感染上下左右四个位置
infect(m, i + 1, j, N, M);
infect(m, i - 1, j, N, M);
infect(m, i, j + 1, N, M);
infect(m, i, j - 1, N, M);
}
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import UnionFind.Application;
import org.junit.Test;

public class UnionFindTest {
@Test
public void countIslandsTest() throws InterruptedException {
int[][] m1 = new int[1000][1000];
int[][] m2 = new int[1000][1000];
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
int temp = (int) (Math.random() * 2);
m1[i][j] = temp;
m2[i][j] = m1[i][j];
}
}
System.out.println("递归感染过程(单线程):" + Application.countIslands(m1));
System.out.println("划分地图,多线程并行:" + Application.countIslandsUnionFind(m2));

}
}

运行结果:

1
2
3
4
递归感染过程(单线程):66575
划分地图,多线程并行:66575

进程已结束,退出代码0

总结

最后划分矩阵分别使用递归,最后合并的代码写了好久。
对Java常用的数据结构还不是很熟悉,又不想改动已经写好的并查集结构。所以写了Node对象,使用nodes数组对矩阵进行复制。
(毕竟要保证并查集中的元素都不一样,虽然值可能一样。而Java中,不new一个Integer对象,而是直接赋值,会自动装箱。自动装箱会将-128~127的数的对象引用指向静态代码块中创建好的对象)
另外,要注意边界的条件。
coding能力有限,只实现了划分一次。
如果是根据矩阵大小动态地划分矩阵,分给多个cpu运算,最后进行合并。会是一个理想的解决方案。
这里就不实现了,练习结束!

顺带一提,时间复杂度的证明比较复杂,所以这里只实现用法和了解大概的复杂度,不深究具体的复杂度及其证明。


参考文章:
并查集基础
算法:并查集
并查集(通俗易懂)
【算法与数据结构】—— 并查集
借这个问题科普一下并查集各种情况下的时间复杂度
并查集
并查集复杂度