並查集演算法中的等級合併與路徑壓縮

稱為並查集（或不相交集）的演算法負責維護不同的集合，並提供操作來驗證集合中的成員資格並將集合組合在一起。它熟練地處理並集和查找操作，這對於維護元素之間的當前連接資訊至關重要。

文法

為了確保清晰度，讓我們先理解即將在接下來的程式碼範例中使用的方法的語法。

// 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中文網其他相關文章！