快捷導(dǎo)航

C++高級數(shù)據(jù)結(jié)構(gòu)之并查集

更新時間：2022年05月24日 09:10:23 作者：下一站不是永遠

這篇文章主要介紹了C高級數(shù)據(jù)結(jié)構(gòu)之并查集,文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下

1.動態(tài)連通性

問題的輸入是一列整數(shù)對，其中每個整數(shù)都表示一個某種類型的對象，一對整數(shù)p和q可以被理解為“p和q是相連的”。我們假設(shè)“相連”是一種等價關(guān)系，這意味著它具有：

自反性：p和p是相連的
對稱性：如果p和q是相連的，那么q和p也是相連的
傳遞性：如果p和q是相連的且q和r是相連的，那么p和r也是相連的

本文中以下內(nèi)容中使用網(wǎng)絡(luò)方面的術(shù)語，將對象稱為觸點，將整數(shù)對稱為連接，將等價類稱為連通分量或是簡稱分量。簡單起見，假設(shè)我們有用0到n-1整數(shù)所表示的N個觸點。這樣做并不會降低算法的通用性。

2.union-find算法API

為了說明問題，我們設(shè)計了一份API來封裝所需的基本操作：初始化、連接兩個觸點、判斷包含某個觸點的分量、判斷兩個觸點是否存在于同一個分量之中以及返回所有分量的數(shù)量。詳細的API如下表所示

為解決動態(tài)連通性問題設(shè)計算法的任務(wù)變成了實現(xiàn)這份API，所有的實現(xiàn)都應(yīng)該：

定義一種數(shù)據(jù)結(jié)構(gòu)表示已知的連接
基于此數(shù)據(jù)結(jié)構(gòu)實現(xiàn)高效的union()、find()、connected() 和count() 方法
實現(xiàn)：

public class UF {
private int[] id; //分量id(以觸點作為索引)
private int count; //分量數(shù)量
public UF(int N) {
//初始化分量id數(shù)組
count = N;
id = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
return -1; //省略此條代碼
}
public void union(int p, int q) {
//見 quick-find、qucik-union、加權(quán)uick-union
}
public static void main(String[] args) {
//解決輸入的連通性問題
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //讀取觸點數(shù)量
UF uf = new UF(N);
while(sc.hasNext()) {
int p = sc.nextInt();
int q = sc.nextInt(); //讀取整數(shù)對
if(uf.connected(p, q)) continue; //如果已連通則忽略
System.out.println("(" + p + ", " + q + ")"); //打印連接
}
System.out.println(uf.count() + "components");
}
}

union-find的成本模型：在研究實現(xiàn)union-find的API的各種算法時，我們統(tǒng)計的是數(shù)組的訪問次數(shù)（訪問任意數(shù)組元素的次數(shù)，無論讀寫）

3.quick-find算法

此方法保證當且僅當id[p] 等于 id[q]時p和q是連通的。換句話說，在同一個連通分量中的所有觸點在id[]中的值必須全部相同。這意味著connected(p, q)只需要判斷id[p] == id[q]，當且僅當p和q在同一連通分量之中該語句才會返回true。為了調(diào)用union(p, q)確保這一點，我們首先要檢查它們是否已經(jīng)存于同一個連通分量之中。如果存在于同一分量中我們不需要采取任何行動，否則我們面對的情況就是p所在的連通分量中的所有觸點的id[]值均為同一個值，而q所在的連通分量中的所有觸點的id[]均為另一個值。要將兩個分量合二為一，我們必須將兩個集合中所有觸點對應(yīng)的id[]元素變?yōu)橥粋€值。為此，我們需要遍歷整個數(shù)組，將所有和id[p]相等的元素的值變?yōu)閕d[q]的值。我們也可以將所有和id[q]相等的元素的值變?yōu)閕d[p]的值，兩者均可。

詳細代碼如下所示：

public class QuickFindUF {
private int[] id; //分量id(以觸點作為索引)
private int count; //分量數(shù)量
public QuickFindUF(int N) {
//初始化分量id數(shù)組
count = N;
id = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
//將p和q歸并到相同的分量中
int pID = find(p);
int qID = find(q);
//如果p和q已經(jīng)在相同的分量之中則不需要采取任何行動
if(pID == qID) return;
//將p的分量重命名為q的名稱
for(int i = 0; i < id.length; i++) {
if(id[i] == pID) id[i] = qID;
}
count--;
}
}

輸出

邊(p,q) id[]
p q -|- 0 1 2 3 4 5 6 7 8 9
-------------------------------------
4 3 -|- 0 1 2 3 3 5 6 7 8 9
3 8 -|- 0 1 2 8 8 5 6 7 8 9
6 5 -|- 0 1 2 8 8 5 5 7 8 9
9 4 -|- 0 1 2 8 8 5 5 7 8 8
2 1 -|- 0 1 1 8 8 5 5 7 8 8
8 9 -|- 0 1 1 8 8 5 5 7 8 8 此時不用做任何改變，8與9已結(jié)處于同一個連通分量中
5 0 -|- 0 1 1 8 8 0 0 7 8 8
7 2 -|- 0 1 1 8 8 0 0 1 8 8
6 1 -|- 1 1 1 8 8 1 1 1 8 8
1 0 -|- 1 1 1 8 8 1 1 1 8 8 此時不用做任何改變，1與0已結(jié)處于同一個連通分量中
6 7 -|- 1 1 1 8 8 1 1 1 8 8 此時不用做任何改變，6與7已結(jié)處于同一個連通分量中

4.quick-union算法

此算法重點提高union()方法的速度，它和quick-find算法是互補的。它也基于相同的數(shù)據(jù)結(jié)構(gòu)----以觸點作為索引的id[]數(shù)組，但我們賦予這些值的意義不同，我們也需要用它們來定義更加復(fù)雜的結(jié)構(gòu)。確切地說，每個觸點對應(yīng)的id[]元素都是同一個分量中另一個觸點的名稱（也可能是它自己）----我們將這種聯(lián)系稱為鏈接。在實現(xiàn)find()方法時，我們從給定的觸點開始，由它的鏈接得到另一個觸點，再由這個觸點到達第三個觸點，如此繼續(xù)跟隨著鏈接直到到達一個根觸點，即鏈接指向自己的觸點（這樣的觸點必然存在）。當且僅當分別由兩個觸點開始的這個過程到達了同一個根觸點時它們存在于同一個連通分量中。為了保證這個過程的有效性，我們需要union(p, q)來保證這一點。它的實現(xiàn)很簡單：我們由p和q的鏈接分別找到它們的根觸點，然后只需將一個根觸點連接到另一個根觸點即可將一個分量重命名為另一個分量，因此這個算法叫做quick-union。和剛才一樣，無論是重命名含有p的分量還是重命名含有q的分量都可以。

實現(xiàn)：

public class QuickUnionUF {
private int[] id; //分量id(以觸點作為索引)
private int count; //分量數(shù)量
public QuickUnionUF(int N) {
//初始化分量id數(shù)組
count = N;
id = new int[N];
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
//找出分量的名稱
while(p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
//將p和q的根節(jié)點統(tǒng)一
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}
}

輸出：

5.加權(quán)quick-union算法

與其在union()中隨意將一棵樹連接到另一棵樹，我們現(xiàn)在會記錄每一棵樹的大小并總是將較小的數(shù)接到較大的樹上。這項改動需要添加一個數(shù)組和一些代碼來記錄樹中的結(jié)點數(shù)，它能夠大大改進算法的效率，提高了查詢根觸點的速度。該算法構(gòu)造的樹的高度遠遠小于未加權(quán)的版本所構(gòu)造的樹的高度。

public class WeightedQuickUnionUF {
private int[] id; //父鏈接數(shù)組(由觸點索引)
private int[] sz; //(由觸點索引的)各個根節(jié)點所對應(yīng)的分量的大小
private int count; //連通分量的數(shù)量
public WeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
sz = new int[N];
for(int i = 0; i < N; i++) sz[i] = 1;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
//跟隨連接找到根節(jié)點
while(p != id[p]) p = id[p];
return p;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
//將小樹的根節(jié)點連接到大樹的根節(jié)點
if(sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else {
id[qRoot] = id[pRoot];
sz[pRoot] += sz[qRoot];
}
count--;
}
}

6.使用路徑壓縮的加權(quán)quick-union算法

理想情況下，我們都希望每個節(jié)點都直接鏈接到它的根節(jié)點上，但我們又不想像quick-union算法那樣通過修改大量鏈接來做到這一點。我們接近這種理想狀態(tài)的方式很簡單，就是在檢查節(jié)點的同時將他們直接鏈接到根節(jié)點。這種方法的實現(xiàn)很容易，而且這些樹并沒有阻止我們進行這種修改的特殊結(jié)構(gòu)：如果這么做能夠改進算法的效率，我們就應(yīng)該實現(xiàn)它。要實現(xiàn)路徑壓縮，只需要為find()添加一個循環(huán)，將在路徑上遇到的所有結(jié)點都直接鏈接到根節(jié)點。我們所得到的結(jié)果是幾乎完全扁平化的樹，它和quick-find算法理想情況下所得到的樹非常接近。這種方法既簡單又高效，但在實際情況下已經(jīng)不太可能對加權(quán)quick-union算法繼續(xù)進行任何改進了。

路徑壓縮的加權(quán)quick-union算法是最優(yōu)的算法

實現(xiàn)：

public class PathCondenseWeightedQuickUnionUF {
private int[] id; //父鏈接數(shù)組(由觸點索引)
private int[] sz; //(由觸點索引的)各個根節(jié)點所對應(yīng)的分量的大小
private int count; //連通分量的數(shù)量
public PathCondenseWeightedQuickUnionUF(int N) {
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
sz = new int[N];
for(int i = 0; i < N; i++) sz[i] = 1;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/*遞歸版本
public int find(int p) {
if(id[p] == p) return p;
id[p] = find(id[p]);
return id[p];
}
*/
public int find(int p) {
int root = p;
while (root != id[root]) {
root = id[root];
}
while (id[p] != root) {
int temp = p;
p = id[p];
id[temp] = root;
}
return root;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
//將小樹的根節(jié)點連接到大樹的根節(jié)點
if(sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else {
id[qRoot] = id[pRoot];
sz[pRoot] += sz[qRoot];
}
count--;
}
}

輸出：