集合与并查集
2024-05-27 13:13:16
发布于：新加坡
在前几篇文章当中，我们已经讨论了许多有关数论的知识点了，因此 Macw 决定写几篇数据结构的文章缓一缓。（整天写数论相关的内容容易自闭（bushi））。
今天我们将会围绕一个新的数据结构，并查集（Disjoint Set Union）来展开。
集合与集合的常见操作
在谈论到并查集的时候，首先讨论一个前置知识点，即 集合（Set）的概念。集合是一种无序且不重复的元素集，用数学可以表示为 ，其中 是这个集合的名字， 等就是这个集合中的元素。
集合的应用非常的广泛。举一个大家生活中都比较熟悉的例子，运动会报名人数统计。假设目前有两个集合，分别表示参加篮球比赛的选手和参加羽毛球比赛的选手，写作：
。
。
对于多个集合而言，设 和 是两个集合，常见的有以下操作：
- 交集（Intersection）：求出两个集合中共同包含的元素，写作 。
- 并集（Union）：求出两个集合中所有的元素并去重，写作 。
- 差集（Difference）：求出在一个集合 中但不在另一个集合 中的元素，写作 。
举例而言：
- 如果我们想要求出既参加了篮球比赛，又参加了羽毛球比赛的同学，可以使用交集操作 。表示 Cindy, Tom 和 Richard 三个人既参加了羽毛球比赛，又同时参加了篮球比赛。
- 同理，如果我们想要求出所有参赛的同学，可以使用并集的操作 。表示这些同学是所有参赛的选手。
- 如果我们想要求出参加了篮球比赛，但没有参加羽毛球比赛的同学，可以使用差集的操作 。表示 Alice, Bob 和 Fred 三人只参加了篮球比赛，没有参加羽毛球比赛。
在介绍完集合的基本操作后，我们将目光着重放在计算 并集 的过程中，这也是今天所要讲的并查集算法的重要组成部分之一。
并查集算法
并查集是一种树形的数据结构，用于处理一些不相交的集合（指的是两个集合的交集为空，即两个集合没有共同的元素），并支持 合并 和 查询 的操作。
- 查询（Find）：查找某个元素所属的集合。通常通过路径压缩（Path Compression）优化，以加快查找速度。
- 合并（Union）：合并两个集合。通常通过按秩合并（Union by Rank）优化，以保证树的高度较低，提高效率。
并查集广泛应用于解决动态连通性问题，如图的连通分量、网络连接、最小生成树等。
并查集代码的实现
在并查集中，每一个集合都可以被看作成一棵树。而集合的标识符也可以被表示为这一棵树的根节点。与此同时，如果在一个场景当中有许多的树，那么这些树将会构成一个森林。
当我们想要找到某一个节点在哪个集合当中，本质上就是在寻找这个节点的根节点编号。若我们想要合并两个集合，本质上就是将一颗树的根节点指向另一棵树的根节点。这样子两棵树就被合并成了一棵树，集合的合并操作也因此完成了。
推荐算法可视化网站：Visualgo.net，各位可以自行访问网站观看并查集算法逻辑的可视化演示。
第一步：定义变量和初始化。
首先，我们需要定义并初始化以个向量/数组，一个用于存储每个元素的父节点。一开始将所有元素的父节点都设置为该节点本身。
vector<int> parent;
void initialize(int n) {
parent.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
第二步：实现查询操作。
接下来，我们实现并查集的 find 操作，用于查找某个元素所属的集合。在查找元素所属的集合时，本质上就是在查找这个集合的父元素。该方法可以通过递归的方式来实现。其中，递归的终止条件就是某一个节点的父节点是该节点本身，代表这个节点是这个集合（树）的根节点。
int find(int x) {
if (parent[x] != x) {
return find(parent[x]);
}
return parent[x];
}
在此基础上，我们还可以对算法进行时间上的优化，也就是对搜寻路径进行压缩。路径压缩的基本思想是在执行查找操作时，将路径上的每个节点都直接连接到根节点上，从而降低整个树的高度。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
路径压缩可以显著减少树的高度，使得查找操作的时间复杂度接近于常数级别，提高了并查集的效率。
第三步：实现合并操作。
然后，我们实现并查集的 union 操作，用于合并两个集合。如果两个元素所指向的父元素是同一个，那么可以说明这两个元素存在于同一个集合当中，不需要进行合并操作。否则就将一个元素添加到另一个集合之中。
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
并查集的时间复杂度
并查集的时间复杂度取决于其两个主要操作：查找 和 合并。
查找操作（Find）
在普通的并查集中，如果不进行路径压缩优化，find 操作的时间复杂度与树的高度成正比。最坏情况下，树的高度可以达到 ，其中 是并查集中元素的数量。
但是，在应用了路径压缩优化的情况下，find 操作的均摊时间复杂度接近于常数级别。具体来说，经过路径压缩的并查集的 find 操作的时间复杂度可以表示为 ，其中 是阿克曼函数的反函数，增长极其缓慢。对于所有实际应用而言，可以将其约等于为常数时间。
合并操作（Union）
合并操作涉及到查找两个元素所在集合的根节点，并将其中一个根节点连接到另一个根节点上。由于查找过程是常数级别的，而合并两棵树的根节点也是常熟级别的，因此合并操作的时间复杂度也近似于常数时间。
总体复杂度
综上所述，经过路径压缩和按秩合并优化后的并查集，在实际应用中具有非常高效的时间复杂度。对于包含 个元素的并查集，其 find 和 union 操作的均摊时间复杂度都接近于常数级别，即 。因此，并查集在解决大规模数据集合动态连通性问题时表现非常出色。
相关引用
- GeeksforGeeks. "Introduction to Disjoint Set Data Structure or Union-Find Algorithm." GeeksforGeeks, 12 May 2023, https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/.
- CP-Algorithms. "Disjoint Set Union." CP-Algorithms, https://cp-algorithms.com/data_structures/disjoint_set_union.html.
- USA Computing Olympiad. "DSU." USA Computing Olympiad, https://usaco.guide/gold/dsu?lang=cpp.
- Halim, Steven, et al. "Union-Find Disjoint Sets (UFDS) - VisuAlgo." VisuAlgo.net
有帮助，赞一个