并查集算法中的等级合并和路径压缩

称为并查集（或不相交集）的算法负责维护不同的集合，并提供操作来验证集合中的成员资格并将集合组合在一起。它熟练地处理并集和查找操作，这对于维护元素之间的当前连接信息至关重要。

语法

为了确保清晰度，让我们首先理解即将在接下来的代码示例中使用的方法的语法。

// 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++ 中实现并查算法的两种不同方法。

方法一：基于数组的实现

在这种方法中，我们将每个集合表示为一个数组。每个索引处的值代表元素的父元素。最初，每个元素都是其自己的父元素，表明它是其集合的代表。

算法

• 让我们开始父数组的初始化过程。每个元素都将被分配其自己的父元素。

• 使用路径压缩实现查找操作。

• 使用 Union by Rank 实现 Union 运算。

示例

#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：基于树的实现

为了描述我们研究中的集合，我们使用了基于树的方法。组中的每个项目都与其各自的父节点关联，同时我们指定根节点来表示该特定集合。

算法

• 初始化父数组，其中每个元素都是其自己的父元素。

• 使用路径压缩和递归树遍历来实现查找操作。

• 使用 Union by Rank 实现 Union 运算。

• 完整的可执行代码

示例

#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++ 可执行代码示例。通过理解和应用按等级并集和路径压缩，您可以增强算法技能并更有效地解决复杂问题。

以上是并查集算法中的等级合并和路径压缩的详细内容。更多信息请关注PHP中文网其他相关文章！