快捷導(dǎo)航

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

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

這篇文章主要介紹了C高級數(shù)據(jù)結(jié)構(gòu)之并查集,文章圍繞主題展開詳細(xì)的內(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ù)語，將對象稱為觸點(diǎn)，將整數(shù)對稱為連接，將等價類稱為連通分量或是簡稱分量。簡單起見，假設(shè)我們有用0到n-1整數(shù)所表示的N個觸點(diǎn)。這樣做并不會降低算法的通用性。

2.union-find算法API

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

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

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

public class UF {
private int[] id; //分量id(以觸點(diǎn)作為索引)
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(); //讀取觸點(diǎn)數(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的成本模型：在研究實(shí)現(xiàn)union-find的API的各種算法時，我們統(tǒng)計(jì)的是數(shù)組的訪問次數(shù)（訪問任意數(shù)組元素的次數(shù)，無論讀寫）

3.quick-find算法

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

詳細(xì)代碼如下所示：

public class QuickFindUF {
private int[] id; //分量id(以觸點(diǎn)作為索引)
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算法

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

實(shí)現(xiàn)：

public class QuickUnionUF {
private int[] id; //分量id(以觸點(diǎn)作為索引)
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é)點(diǎn)統(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ù)接到較大的樹上。這項(xiàng)改動需要添加一個數(shù)組和一些代碼來記錄樹中的結(jié)點(diǎn)數(shù)，它能夠大大改進(jìn)算法的效率，提高了查詢根觸點(diǎn)的速度。該算法構(gòu)造的樹的高度遠(yuǎn)遠(yuǎn)小于未加權(quán)的版本所構(gòu)造的樹的高度。

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

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

實(shí)現(xiàn)：

public class PathCondenseWeightedQuickUnionUF {
private int[] id; //父鏈接數(shù)組(由觸點(diǎn)索引)
private int[] sz; //(由觸點(diǎn)索引的)各個根節(jié)點(diǎn)所對應(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é)點(diǎn)連接到大樹的根節(jié)點(diǎn)
if(sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else {
id[qRoot] = id[pRoot];
sz[pRoot] += sz[qRoot];
}
count--;
}
}

輸出：