動態連通性問題（並查集）

08-31

動態連通性問題（並查集）

來自專欄演算法（第四版）學習筆記4 人贊了文章

1.問題描述：

有N個對象，對象間可以連通。假設有一個命令用來連接兩個對象，將兩個對象傳入該命令就會連接兩者，還有一個命令來查詢任意兩個對象之間是否有連通的路徑存在（間接相連也算）。以上即：合併命令、查找命令。

連接是個等價關係，滿足傳遞性、自反性、對稱性等。
連通分量：相互連接的對象的最大集合，連通分量重的任意兩個對象都是相連接的。

2.快速查找演算法：

2.1演算法描述（貪心）：

維護一個簡單的對象索引整數數組，相互連通的對象對應的數組值相等，不連通的不相等。

查找：如果p和q對應的數組值相同則它們倆連通。
連通：將兩組索引id轉為一致。

效率：初始化O(n)，並O(n)，查O(1)。如果要在n個對象上進行n次合併操作，則是O(n2)，很不合理。

2.2代碼實現：

public class UF{ private int[] id; UF(int N){ //構造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//並 int pid = id[p]; int qid = id[q]; for(int i = 0;i < id.length;i ++) if(id[i] == pid) id[i] = qid; } boolean connected(int p,int q){//查 return id[p] == id[q]; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } }}# 3.快速合併演算法

3.快速合併演算法：

3.1演算法描述：運用了懶計算的思路，維護一棵樹，id[i]記錄著i的父節點。

查找就是找p和q是否有同一祖先節點。
合併p和q就是將p的祖先節點置為q的祖先節點，反之亦可。

初始化O(n)，並O(n)，查O(n)。如果樹特別高，則查特別耗時。# 3.2代碼實現：

public class UF{ private int[] id; UF(int N){ //構造器 id = new int[N]; for(int i = 0;i < N;i++) id[i] = i; } void union(int p,int q){//並 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; id[p] = q; } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } }}

4.快速合併演算法改進演算法1：

4.1演算法描述：我們要避免得到很高的樹，當一顆大樹和一顆小樹合併，避免將大樹放到小樹下面（這樣會使樹變高）。

用加權實現，權重是每棵樹中對象的個數。通過確保將小樹的根節點作為大樹的根節點的子節點以維持平衡。初始化O(n)，並O(logn) ，查O(logn)，因為任意節點X的深度最多是logn。4.2快速合併演算法改進演算法代碼實現：

public class UF{ private int[] id; UF(int N){ //構造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//並 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]) p = id[p] while(q != id[q]) q = id[q]; return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } }}

5.快速合併演算法改進演算法2：

5.1演算法描述：

使用路徑壓縮的加權演算法，即當我們經過」遞推」找到祖先節點後，」回溯」的時候順便將它的子孫節點都直接指向祖先，這樣以後再次查時複雜度就變成O(1)了，再回溯一次將樹展平。這是最優演算法。

初始化O(n)，並和查都非常接近但是仍沒達到1（均攤成本）。

5.2演算法代碼：

public class UF{ private int[] id; UF(int N){ //構造器 id = new int[N]; sz = new int[N]; for(int i = 0;i < N;i++) id[i] = i; sz = 1; } void union(int p,int q){//並 while(p != id[p]){ id[p] = id[id[p]]; p = id[p] } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } if(p == 1) return; if(sz[p] < sz[q]) {id[p] = q;sz[p]+= sz[q];} else {id[q] = p;sz[q]+= sz[p];} } boolean connected(int p,int q){//查 while(p != id[p]){ id[p] = id[id[p]]; p = id[p]; } while(q != id[q]){ id[q] = id[id[q]]; q = id[q]; } return p == q; } public static void main(String args[]){ int N = StdIn.readInt(); UF uf = new UF(N); while(!StdIn.isEmpty()){ int p = StdIn.readInt(); int q = StdIn.readInt(); if(!uf.connected(p,q)){ uf.union(p,q); StdOut.println(p + " " + q); } } }}