数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学并查集算法中的按秩合并和路径压缩
并查集（或不相交集）算法负责维护不相交的集合，并提供操作来检查集合成员资格以及合并集合。它巧妙地处理了并集和查找操作，这两个操作对于维护元素之间当前的连接信息至关重要。
语法
为了清晰起见，让我们首先理解将在接下来的代码示例中使用的那些方法的语法。
// Method to perform Union operation void Union(int x, int y); // Method to find the representative element of a set int Find(int x);
算法
并查集算法包含两个基本操作——并集和查找。并集操作合并两个集合，而查找操作确定集合的代表元素。通过迭代地应用并集和查找操作，我们可以构建一个高效的并查集数据结构。
按秩合并
按秩合并技术用于优化并集操作，方法是确保总是将较小的树附加到较大的树的根节点。这种方法可以防止树变得过于不平衡，这会导致查找操作效率低下。
按秩合并的算法如下：
找到包含元素 x 和 y 的集合的代表元素（根元素）。
如果代表元素相同，则返回。
如果 x 的代表元素的秩大于 y 的代表元素的秩，则使 y 的代表元素指向 x 的代表元素，并更新 x 的代表元素的秩。
否则，使 x 的代表元素指向 y 的代表元素，并在必要时更新 y 的代表元素的秩。
路径压缩
路径压缩是另一种优化技术，它减少了并查集数据结构中树的高度。它旨在在查找操作期间展平路径，从而为后续操作产生更短的路径。
路径压缩的算法如下：
找到包含元素 x 的集合的代表元素（根元素）。
在从 x 到其代表元素的路径上遍历时，使每个访问的元素直接指向代表元素。
方法
现在我们已经理解了按秩合并和路径压缩的基本概念，让我们讨论两种在 C++ 中实现并查集算法的不同方法。
方法 1：基于数组的实现
在这种方法中，我们将每个集合表示为一个数组。每个索引处的数值表示元素的父元素。最初，每个元素都是它自己的父元素，这表示它是其集合的代表元素。
算法
让我们开始父数组的初始化过程。每个元素将被赋予它自己的父元素。
使用路径压缩实现查找操作。
使用按秩合并实现并集操作。
示例
#include <iostream>
#define MAX_SIZE 100
// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];
void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
void Union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
// Union by rank
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() {
// Usage example
makeSet(10); // Assuming 10 elements in the set
Union(1, 2);
Union(3, 4);
// Print parent array
for (int i = 0; i < 10; i++) {
std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
}
return 0;
}
输出
Element 0 Parent: 0 Element 1 Parent: 1 Element 2 Parent: 1 Element 3 Parent: 3 Element 4 Parent: 3 Element 5 Parent: 5 Element 6 Parent: 6 Element 7 Parent: 7 Element 8 Parent: 8 Element 9 Parent: 9
方法 2：基于树的实现
为了在我们的研究中描述集合，我们使用基于树的方法。组内的每个项目都与其各自的父节点关联，而我们将根节点指定为代表该特定集合。
算法
初始化父数组，其中每个元素都是它自己的父元素。
使用路径压缩和递归树遍历实现查找操作。
使用按秩合并实现并集操作。
完整的可执行代码
示例
#include <iostream>
#define MAX_SIZE 100
// Initialize parent array
int parent[MAX_SIZE];
int rank[MAX_SIZE];
void makeSet(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
void Union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
}
// Union by rank
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() {
// Usage example
makeSet(10); // Assuming 10 elements in the set
Union(1, 2);
Union(3, 4);
// Print parent array
for (int i = 0; i < 10; i++) {
std::cout << "Element " << i << " Parent: " << parent[i] << std::endl;
}
return 0;
}
输出
Element 0 Parent: 0 Element 1 Parent: 1 Element 2 Parent: 1 Element 3 Parent: 3 Element 4 Parent: 3 Element 5 Parent: 5 Element 6 Parent: 6 Element 7 Parent: 7 Element 8 Parent: 8 Element 9 Parent: 9
结论
总之，按秩合并和路径压缩是并查集算法中的关键技术。它们分别优化了并集和查找操作，从而提高了性能并实现了高效的连接信息管理。通过在 C++ 中实现这些技术，我们可以有效地解决与集合、连接和图相关的难题。
总而言之，我们涵盖了语法、分步算法，并提供了两个真实的 C++ 可执行代码示例。通过理解和应用按秩合并和路径压缩，您可以提高您的算法技能，并更有效地解决复杂的问题。
3000+ 次浏览
