极客笔记C++ 介绍不相交集数据结构或并查集算法
不相交集信息结构，也称为并查集算法，是计算机科学中一个重要的概念，它提供了一种有效的解决分配和网络相关问题的方法。它在解决包含组件集合和确定它们之间连接的问题方面特别有价值。在本文中，我们将探讨C++中实现该不相交集信息结构的语法、算法和两种不同的方法。我们还将提供完全可执行的代码示例来说明这些方法。
语法
在深入研究算法之前，让我们先熟悉以下代码示例中使用的语法-
// Create a disjoint set
DisjointSet ds(n);
// Perform union operation
ds.unionSets(a, b);
// Find the representative of a set
ds.findSet(x);
步骤
在处理多个不相关的集合时，利用不相交数据结构可以很有用。每个单独的分组都有一个特定的代表来描述它。起始点涉及每个组件形成自己的孤立集，与其各自的代表相对应（它本身也是代表）。不相交集上执行的两个主要操作是联合和查找。
联合操作
- 找到要合并的两个集合的代表。
-
如果代表不同，使一个代表指向另一个代表，有效地合并集合。
-
如果代表相同，则集合已经合并，不需要进一步操作。
查找操作
-
给定一个元素，找到它所属集合的代表。
-
沿着父指针追踪，直到达到代表。
-
将代表作为结果返回。
方法1：基于等级和路径压缩的联合
实现不相交集数据结构的一个高效方法是使用基于等级和路径压缩的联合技术。
在这种方法中，每个集合都有一个相关联的等级，初始设为0。
在两个集合之间执行联合操作时，优先选择具有较高等级的集合，并将其合并到具有较低等级的集合中。如果两个集合的等级相同，则必须随机选择一个集合合并到另一个集合中。无论哪种情况，一旦合并成一个新集合，其等级增加1。此外，为了加快查找操作并减少时间复杂度，路径压缩可在这些操作期间使树结构变平。
示例
#include <iostream>
#include <vector>
class DisjointSet {
std::vector<int> parent;
std::vector<int> rank;
public:
DisjointSet(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i)
parent[i] = i;
}
int findSet(int x) {
if (parent[x] != x)
parent[x] = findSet(parent[x]);
return parent[x];
}
void unionSets(int x, int y) {
int xRoot = findSet(x);
int yRoot = findSet(y);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else if (rank[xRoot] > rank[yRoot])
parent[yRoot] = xRoot;
else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
};
int main() {
// Example usage of DisjointSet
int n = 5; // Number of elements
DisjointSet ds(n);
ds.unionSets(0, 1);
ds.unionSets(2, 3);
ds.unionSets(3, 4);
std::cout << ds.findSet(0) << std::endl;
std::cout << ds.findSet(2) << std::endl;
return 0;
}
输出
0
2
方法2：基于大小的按大小合并与路径压缩
另一种处理不相交集数据结构的方法是使用按大小合并与路径压缩技术。
- 在这种方法中，每个集合都有一个关联的大小，初始设置为1。
-
在合并操作期间，较小的集合将合并到较大的集合中。
-
相应地更新所得到的集合的大小。
-
在查找操作期间，应用路径压缩来扁平化树结构，与之前的方法类似。
示例
#include <iostream>
#include <vector>
class DisjointSet {
std::vector<int> parent;
std::vector<int> size;
public:
DisjointSet(int n) {
parent.resize(n);
size.resize(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}
int findSet(int x) {
if (parent[x] != x)
parent[x] = findSet(parent[x]);
return parent[x];
}
void unionSets(int x, int y) {
int xRoot = findSet(x);
int yRoot = findSet(y);
if (xRoot == yRoot)
return;
if (size[xRoot] < size[yRoot]) {
parent[xRoot] = yRoot;
size[yRoot] += size[xRoot];
}
else {
parent[yRoot] = xRoot;
size[xRoot] += size[yRoot];
}
}
};
int main() {
// Example usage of DisjointSet
int n = 5; // Number of elements
DisjointSet ds(n);
ds.unionSets(0, 1);
ds.unionSets(2, 3);
ds.unionSets(3, 4);
std::cout << ds.findSet(0) << std::endl;
std::cout << ds.findSet(2) << std::endl;
return 0;
}
输出
0
2
结论
不相交集数据结构，或者并查集算法，是解决涉及集合和连通性问题的强大工具。本文详细讨论了C++的不相交集数据结构语法和算法。为了增进我们的理解，我们提供了两种独特的方法- 基于排名的并查集结合路径压缩，以及基于大小的并查集通过大小加上路径压缩。通过理解和实现这些方法，您可以高效地解决各种需要跟踪不相交集合的问题。