資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究不相交集資料結構或並查集演算法簡介
不相交集資訊結構，也稱為並查集演算法，是計算機科學中的一個重要概念，它提供了一種有效的方法來解決與分割槽和網路相關的 問題。它在解決涉及元件集並確定它們之間連線的問題方面尤其有價值。在本文中，我們將探討 C++ 中不相交集資訊結構的語法、演算法和兩種不同的實現方法。我們還將提供完全可執行的程式碼示例來說明這些方法。
語法
在深入研究演算法之前，讓我們先熟悉一下以下程式碼示例中使用的語法。
// Create a disjoint set DisjointSet ds(n); // Perform union operation ds.unionSets(a, b); // Find the representative of a set ds.findSet(x);
演算法
在處理多個不相交集時，使用不相交集資料結構可能很有用。每個組都由一個特定的代表來標識。開始時，每個元件都形成自己的獨立集，對應於其相應的代表（也正好是自己）。在不相交集上執行的兩個主要操作是 union（合併）和 find（查詢）。
合併操作
找到要合併的兩個集合的代表。
如果代表不同，則使一個代表指向另一個，從而有效地合併集合。
如果代表相同，則集合已經合併，無需進一步操作。
查詢操作
給定一個元素，找到它所屬集合的代表。
沿著父指標一直找到代表。
返回代表作為結果。
方法 1：基於秩的合併和路徑壓縮
實現不相交集資料結構的一種有效方法是使用基於秩的合併和路徑壓縮技術。
在這種方法中，每個集合都有一個關聯的秩，初始設定為 0。
在執行兩個集合之間的合併操作時，優先考慮秩較高的集合，並將秩較低的集合合併到秩較高的集合中。如果兩個集合的秩相同，則需要任意選擇一個集合來合併另一個集合。在任何一種情況下，一旦合併成一個新的集合，它的秩就會增加 1。此外，為了加速查詢操作並降低時間複雜度，路徑壓縮有助於在這些操作期間使樹結構扁平化。
示例
#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。
在合併操作期間，較小的集合將合併到較大的集合中。
相應地更新結果集合的大小。
路徑壓縮應用於查詢操作，以使樹結構扁平化，類似於先前的方法。
示例
#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++ 中不相交集資料結構的語法及其演算法。為了擴充套件我們的理解，我們為讀者提供了兩種獨特的方法——基於秩的合併結合路徑壓縮，以及基於大小的合併加路徑壓縮。透過理解和實現這些方法，您可以有效地解決需要跟蹤不相交集的各種問題。
1K+ 瀏覽量
