不相交集合数据结构或并查集算法介绍

不相交集信息结构，也称为并查算法，可能是计算机科学中的一个基本概念，它为解决与分配和网络相关的问题提供了有效的方法。它对于解决包括组件集和确定它们的连接在内的问题特别有价值。在本文中，我们将研究语言结构、算法以及在 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：通过大小和路径压缩进行基于大小的合并

另一种处理不相交集合数据结构的方法是使用按大小合并和路径压缩技术。

• 在此方法中，每个集合都有一个关联的大小，最初设置为 1。

• 在并集操作中，较小的集合被合并到较大的集合中。

• 结果集的大小会相应更新。

• 在查找操作期间应用路径压缩以展平树结构，类似于之前的方法。

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

结论

不相交集合数据结构或并查算法是解决涉及集合和连通性问题的强大工具。本文广泛研究了 C++ 的不相交集数据结构语法及其算法。为了扩展我们的理解，我们为读者提供了两种独特的方法 - 基于排名的并集与路径压缩相结合，以及通过大小加路径压缩进行基于大小的并集。通过理解和实现这些方法，您可以有效地解决需要跟踪不相交集的各种问题。

以上是不相交集合数据结构或并查集算法介绍的详细内容。更多信息请关注PHP中文网其他相关文章！