不相交集合資料結構或併查集演算法介紹

不相交集資訊結構，也稱為並查演算法，可能是電腦科學中的一個基本概念，它為解決與分配和網路相關的問題提供了有效的方法。它對於解決包括組件集和確定它們的連接在內的問題特別有價值。在本文中，我們將研究語言結構、演算法以及在 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中文網其他相關文章！