不相交集信息结构，也称为并查算法，可能是计算机科学中的一个基本概念，它为解决与分配和网络相关的问题提供了有效的方法。它对于解决包括组件集和确定它们的连接在内的问题特别有价值。在本文中，我们将研究语言结构、算法以及在 C++ 中执行不相交集合信息结构的两种独特方法。我们还将提供完全可执行的代码示例来说明这些方法。
语法
在深入研究算法之前，让我们先熟悉一下以下代码示例中使用的语法 -
// Create a disjoint set
DisjointSet ds(n);
// Perform union operation
ds.unionSets(a, b);
// Find the representative of a set
ds.findSet(x);
算法
处理多个不关联的集合时，利用不相交的数据结构可能非常有用。每个单独的分组都指定有一个特定的代表来表征它。起点涉及每个组件形成其自己的隔离集，该隔离集与其各自的代表相对应（也恰好是其自身）。对不相交集执行的两个主要操作是并集和查找。
联合操作
查找操作
给定一个元素，找到它所属集合的代表。
跟随父指针直到达到代表节点。
将代表作为结果返回。
方法一：基于排名的按秩合并和路径压缩
实现不相交集数据结构的一种有效方法是使用按等级并集和路径压缩技术。
在此方法中，每个集合都有一个关联的排名，最初设置为 0。
在两个集合之间执行并集运算时，优先考虑排名较高的集合，并合并排名较低的集合。如果两个集合具有相似的等级，则必须任意选择哪个集合包含谁。在任何一种情况下，一旦合并到新集合中，其排名都会增加 1。此外，为了加快查找操作并降低时间复杂度，路径压缩有助于在这些操作期间压平树结构。
Example
的中文翻译为：示例
#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：通过大小和路径压缩进行基于大小的合并
另一种处理不相交集合数据结构的方法是使用按大小合并和路径压缩技术。
Example
的中文翻译为：示例
#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
结论
不相交集合数据结构或并查算法是解决涉及集合Ø
.........................................................