并查集算法总结
先挂偶像公开课的链接:https://www.coursera.org/learn/algorithms-part1/home/welcome。
本文是自己算法理解的一个记录,表达的不够清楚勿喷,如果有收获,也可以留言点个赞。
算法概述
概述引用维基百科
在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作:
Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union:将两个子集合并成同一个集合。
解题一:自己写的暴力解题法,见笑了
暴力解题,只适合很小规模的数据量,数据量大就炸了。
数据结构:创建一个数组,每个数组中再创建一个数组,用来保存子集。
合并操作:找出两个子集的index,然后合并为一个。
查询两数联通:分别查询两个数归属的子集的index,判断index是否相同,相同便是联通。
查询归属子集:遍历查询归属那个子集。:(
主要代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
private List<List<Integer>> components;
//初始化 - time complexity: N
for (int i = 0; i < N; i++) {
List<Integer> component = new ArrayList<>();
component.add(i);
components.add(component);
}
//查找index - time complexity: N²
for (List<Integer> component : components) {
for (Integer z : component) {
if (p == z) {
return components.indexOf(component);
}
}
}
//合并 - time complexity: N²+
int pidx = find(p);
int qidx = find(q);
if (pidx != qidx) {
List<Integer> qcomponent = components.get(qidx);
List<Integer> pcomponent = components.get(pidx);
pcomponent.addAll(qcomponent);
components.remove(qidx);
}
|
解题二:快速查找
明白数据结构就一气呵成了,简单写了。此算法也不适合大规模数据使用,因为合并算法的时间复杂度为线性的。
数据结构:创建一个数组,合并就是把数组中的内容修改为相同的数,这样就可以判断是否是同一子集了。
部分代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//初始化 N
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
//查询 1
return id[p];
//合并 N(两个子集合并,需要循环修改数组中的内容)
int pid = find(p);
int qid = find(q);
for (int i = 0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
|
解题三:快速合并
该算法性能也差,时间复杂度都是线性的,但是数型结构后续优化潜力大。
数据结构,树型结构,合并时把被合并数指向合并数即可,也是只需要一个数组,用来保存该数指向那个节点。
合并操作:把被合并数的根节点指向合并数的根节点即可
查询归属子集:查询根节点
查询是否联通:查询两个数是否拥有同一个根节点
主要代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
//初始化 同上 - N
//寻找根节点 N(取决于树的高度)
while (i != id[i]) {
i = id[i];
}
return i;
//合并 - N(取决于树的高度)
if (!connected(p, q)) {
int i = root(p);
int j = root(q);
id[i] = j;
}
//查询联通 - N(取决于树的高度)
return root(p) == root(q);
|
解题四:在快速合并算法的基础上进行优化
思考一下,快速合并为什么慢,主要是因为查找根节点的时候,树存在细长的情况,也就是高度高,造成高度高的主要原因是什么?或者说是什么操作造成的高度增长?对,是合并操作,所以需要思考合并的时候能有什么优化。
优化一:权重(也可以理解为树的大小)
合并时考虑权重,把权重低的树向权重高的树合并,理论上讲树的高度不会超过lgN(简单证明过程可以看开头提到的视频)。
需要一个额外的数组来保存节点权重。
优化代码
1
2
3
4
5
6
7
8
9
10
11
12
|
private int[] size;
//初始时全部初始化成1
size[i] = 1;
// 合并操作,重量小的向重量大的合并,建立一个数组来记录相应root节点的权重
// 巨大优化,合并查询操作时间复杂度提升到对数级别。
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = id[rootP];
size[rootP] += size[rootQ];
}
|
优化二
我们可以进一步缩小树的高度,在计算根节点时,会顺序遍历子链中子节点,为了减少链的长度,把当前节点指向上上个节点,这样整棵树子节点更平。
代码
用偶像的话来说,one line code, amazing
总结
并查集算法是比较基础的算法,需要透彻的理解,数据结构并不复杂,算法思路也不复杂。