并查集算法中的按秩合并和路径压缩

并查集（或不相交集）算法负责维护不相交的集合，并提供操作来检查集合成员资格以及合并集合。它巧妙地处理了并集和查找操作，这两个操作对于维护元素之间当前的连接信息至关重要。

语法

为了清晰起见，让我们首先理解将在接下来的代码示例中使用的那些方法的语法。

// 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 到其代表元素的路径上遍历时，使每个访问的元素直接指向代表元素。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

方法

现在我们已经理解了按秩合并和路径压缩的基本概念，让我们讨论两种在 C++ 中实现并查集算法的不同方法。

方法 1：基于数组的实现

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

算法

  • 让我们开始父数组的初始化过程。每个元素将被赋予它自己的父元素。

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

  • 使用按秩合并实现并集操作。

示例

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

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

算法

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

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

  • 使用按秩合并实现并集操作。

  • 完整的可执行代码

示例

Open Compiler
#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++ 可执行代码示例。通过理解和应用按秩合并和路径压缩，您可以提高您的算法技能，并更有效地解决复杂的问题。

更新于：2023年7月25日

3000+ 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告