1.什么是并查集
并查集是用来管理元素分组的数据结构。可以高效进行如下操作：
- 查询元素a、b十是否在同一组
- 合并a、b所在的组
并查集可以进行合并操作但不能进行分割操作。
2.并查集的结构
并查集采用多叉树形结构实现，每个元素对应一个结点，每个组对应一棵树。重点关注结整体形成一个树形结构，而不是树的形状等信息。
3.并查集的实现
3.1 初始化
对于并查集，一般采用数组来实现，其中元素为数组的索引，其父辈为数组索引对应内容。
在初始化中，将每个元素父辈设为自己，即自己形成一组，并对用一个rank数组记录以每个元素为根的树的层数，以方便后面并查集优化的实现。
UnionFind(int count)
{
parent = new int[count];
rank = new int[count];
this->count = count;
for (int i = 0; i < count; ++i)
{
parent[i] = i;
rank[i] = 1;
}
}
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| parent | 1 | 2 | 3 | 4 | 5 |
3.2 查找
为了查询两个节点否属于同一数组，需要采用查找两个节点的根，通过判断根是否相同来判断元素是否相同的方法。故查找用于实现查找元素的根。
在查找过程中采用路径压缩对组内进行优化，将树的层数降低，从而降低查找的复杂度，通常有两种压缩方法：
-
采用递归实现，在查询过程中向上经过的所有节点都直接连到根上，将路径压缩至如下状态，使得查找时间复杂度降为 O(1)，但路径压缩的过程则比较耗费时间。
int find(int p)
{
assert(p >= 0 && p < count);
/***** 路径压缩一：压缩过程耗时 *****/
if(p != parent[p])
parent[p] = find(parent[p]); //递归实现路径压缩，最终find时间复杂度为 O(1)
return parent[p];
}
-
采用循环，在查询过程中，将当前结点的父辈更改为当前父辈的父辈，则将路径压缩至如下状态，查找时间复杂度虽然未达到最优，但压缩时间开销相对较小。
int find(int p)
{
assert(p >= 0 && p < count);
/***** 路径压缩二：压缩过程快，find时间复杂度未达到 O(1) *****/
while (p != parent[p])
{
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
3.3 合并
将一组元素的根指向另一组元素的根，就实现了元素的合并：
- 因为只要属于两个组的元素进行了合并，就相当于这两个组合并了。故两元素合并时先找到其所在组的根，再把根合并。
- 在合并过程中，需要将层数低的数指向层数高的，以有效降低合并后树的高度，这时候就用到了我们初始化时使用的 rank 数组。
void unionElements(int p, int q)
{
//合并优化，降低层数
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
if(rank[pRoot] > rank[qRoot])
{
parent[qRoot] = pRoot;
}
else if(rank[pRoot] < rank[qRoot])
{
parent[pRoot] = qRoot;
}
else
{ //rank[pRoot] == rank[qRoot]的情况
parent[qRoot] = pRoot;
rank[pRoot] += 1;
}
}
3.4 判断两元素是否如同组
判断元素的根是否相同，具体实现如下：
bool isconnected(int p, int q)
{
return find(p) == find(q);
}
4.小结
- 通过优化后的并查集效率非常高。对于 n 个元素进行一次操作的复杂度时 O(a(n))。 a(n)时阿克曼(Ackermann)函数的反函数，比 O(log(n)) 还快。
- 在最小生成树算法 Kruskal 中，需要判断一条边的两个顶点是否属于同一个连通分量，这时候需要并查集来进行高效的判断。
