資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學並查集演算法中的按秩合併和路徑壓縮
並查集（或不相交集）演算法負責維護不相交的集合，並提供操作來檢查集合成員資格以及合併集合。它巧妙地處理了並集和查詢操作，這兩個操作對於維護元素之間當前的連線資訊至關重要。
語法
為了清晰起見，讓我們首先理解將在接下來的程式碼示例中使用的那些方法的語法。
// 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++ 中實現並查集演算法的不同方法。
方法 1：基於陣列的實現
在這種方法中，我們將每個集合表示為一個數組。每個索引處的數值表示元素的父元素。最初，每個元素都是它自己的父元素，這表示它是其集合的代表元素。
演算法
讓我們開始父陣列的初始化過程。每個元素將被賦予它自己的父元素。
使用路徑壓縮實現查詢操作。
使用按秩合併實現並集操作。
示例
#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：基於樹的實現
為了在我們的研究中描述集合，我們使用基於樹的方法。組內的每個專案都與其各自的父節點關聯，而我們將根節點指定為代表該特定集合。
演算法
初始化父陣列，其中每個元素都是它自己的父元素。
使用路徑壓縮和遞迴樹遍歷實現查詢操作。
使用按秩合併實現並集操作。
完整的可執行程式碼
示例
#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++ 可執行程式碼示例。透過理解和應用按秩合併和路徑壓縮，您可以提高您的演算法技能，並更有效地解決複雜的問題。
3000+ 次瀏覽
