詳細(xì)解析參照算法(第4版)1.5章——案例研究:union—find算法

1.union-find法的API

public class UF	?
UF(int N)	以整數(shù)標(biāo)識(0—N-1)初始化N個標(biāo)識
void union(int p,int q)	在觸點(diǎn)p和q之間添加一條連接
void find(int p)	p所在連通分量的標(biāo)識符(0—N-1)
void connected(int p,int q)	判斷觸點(diǎn)p和q是否連通，即p和q是否在同一連通分量
int count()	連通分量的數(shù)目

?

2.union-find的實(shí)現(xiàn)

1: public abstract class UF { 2: protected int count; 3: protected int[] id; 4:? 5: public UF(int N) { 6: count = N; 27: if (find(i) == pID) 7: id = new int[N]; 8: for (int i = 0; i < N; i++) 9: id[i] = i; 10: } 11: 12: public abstract int find(int p); 13: 14: public abstract void union(int p,int q); 15: 16: public boolean connected(int p,int q){ 17: return find(p) == find(q); 18: } 19: 20: public int count(){ 21: return count; 22: } 23: }

2.1.quick-find算法

1: public class QuickFindUF extends UF { 2:? 3: public QuickFindUF(int N) { 4: super(N); 5: } 6:? 7: @Override 8: public int find(int p) { 9: // TODO Auto-generated method stub 10: // 觸點(diǎn)p為索引，id[p]即是p所在的連通分量的標(biāo)識符 11: return id[p]; 12: } 13:? 14: /** 15: * 如果p和q在同一個連通分量，則p和q連通 否則，要將p和q連通(兩個連通分量合并)，即將p的連通分量所有觸點(diǎn)的連通分量改成q的連通分量 16: */ 17: @Override 18: public void union(int p, int q) { 19: // TODO Auto-generated method stub 20: int pID = find(p); 21: int qID = find(q); 22:? 23: if (pID == qID) 24: return; 25:? 26: for (int i = 0; i < id.length; i++) 27: if (find(i) == pID) 28: id[i] = qID; 29: count--; 30: } 31: 32: 33:? 34: }

?

算法分析

?????? 1.union(p,q)會訪問數(shù)組次數(shù)N+3~2N+1

?????? 分析：(1)兩次find()操作，訪問2次數(shù)組

????????????????? (2)掃描整個數(shù)組id[]，判斷p和q是否在同一個連通f分量if(find(i)==pID)，訪問N次數(shù)組

????????????????? (3)①只有p，其余觸點(diǎn)均不和p在同一連通分量 id[p] =qID,訪問1次數(shù)組

????????????????????? ②除了q本身，其余均和p在同一連通分量 id[i] = qID(i≠q)，訪問 N-1次數(shù)組，故總的訪問次數(shù)①2+N+1 = N+3??????? ②2+N+N-1 = 2N+1

?????? 2.在最好的情況下(union(p,q)訪問數(shù)組N+3次)，N個整數(shù)要進(jìn)行N-1次合并union(p,q)操作，訪問數(shù)組(N+3)(N-1)~N^2。

? ? ? ?quick-union算法是平方級別的。

測試結(jié)果

1: public static void main(String[] args) { 2: DirectInput.directInput(args); 3: int N = StdIn.readInt(); 4: UF uf = new QuickFindUF(N); 5: while(!StdIn.isEmpty()){ 6: int p = StdIn.readInt(); 7: int q = StdIn.readInt(); 8: if(uf.connected(p, q) ) continue; 9: uf.union(p, q); 10: StdOut.println(p+ " " + q); 11: } 12: 13: StdOut.println(uf.count() + " components"); 14: }

?

2.2.quick-union算法

1: /** 2: * 以觸點(diǎn)p為索引的數(shù)組id[p]是p所在的連通分量中的另一個觸點(diǎn)q<br> 3: * 即p與q是連通的 4: * 5: * @author YoungCold 6: * 7: */ 8: public class QuickUnionUF extends UF { 9:? 10: public QuickUnionUF(int N) { 11: super(N); 12: } 13:? 14: /** 15: * 找到p的根觸點(diǎn)<br> 16: * 根觸點(diǎn):符合id[p]=p，即指向自己的觸點(diǎn)，即為根觸點(diǎn) 17: */ 18: @Override 19: public int find(int p) { 20: // TODO Auto-generated method stub 21: while (p != id[p]) 22: p = id[p]; 23: return p; 24: } 25:? 26: /** 27: * 當(dāng)p的根觸點(diǎn)和q的根觸點(diǎn)不同時，說明p和q不在同一個連通分量<br> 28: * 要想p和q連通，即將p(q)的根觸點(diǎn)(id值為本身)指向q(p)的根觸點(diǎn) 29: */ 30: @Override 31: public void union(int p, int q) { 32: // TODO Auto-generated method stub 33: int pRoot = find(p); 34: int qRoot = find(q); 35:? 36: if (pRoot == qRoot) 37: return; 38:? 39: // 將p的根觸點(diǎn)(id值為本身)指向q的根觸點(diǎn) 40: id[pRoot] = qRoot; 41: //每次合并，連通分量的數(shù)目減一 42: count--; 43: } 44:? 45: public static void main(String[] args) { 46: DirectInput.directInput(args); 47: int N = StdIn.readInt(); 48: UF uf = new QuickUnionUF(N); 49: for (int i = 0; i < N; i++) { 50: int p = StdIn.readInt(); 51: int q = StdIn.readInt(); 52: if (uf.connected(p, q)) 53: continue; 54:? 55: uf.union(p, q); 56: StdOut.println(p + " " + q); 57: } 58: StdOut.println(uf.count() + " components"); 59: } 60:? 61: }

(1)與quick-find不同的是，以觸點(diǎn)p為索引的數(shù)組id[]不再表示p所在的連通分量，而是表示p所在的連通分量的另一個觸點(diǎn)(也可能是它本身)，當(dāng)它是本身時，該觸點(diǎn)就是根觸點(diǎn)，也就是連通分量所對應(yīng)的樹的根節(jié)點(diǎn)，這種聯(lián)系稱之為鏈接。

(2)森林的表示，實(shí)際上id[]數(shù)組用父鏈接的形式表示了一片森林。無論從任何觸點(diǎn)所對應(yīng)的節(jié)點(diǎn)開始跟蹤鏈接，最終都能到達(dá)含有該節(jié)點(diǎn)的樹的根節(jié)點(diǎn)(可用數(shù)學(xué)歸納法證明)。

?

算法分析

? ? ? ?1.quick-union算法看似比quick-find算法塊，因?yàn)樗恍枰獮槊繉斎氡闅v整個數(shù)組。

??????? 2.①最好的情況下find(p),僅訪問一次數(shù)組，此時觸點(diǎn)p為根觸點(diǎn)。

????????? ②最壞的情況下find(p),訪問數(shù)組2N-1次

????????????? while(p != id[p]) p = id[p];

???????????? 最壞的情況是觸點(diǎn)p所在的連通分量對應(yīng)的樹退化成線性表而且僅有一個連通分量,而p在線性表的表尾。

???????????? while()循環(huán)的判斷條件要訪問N次數(shù)組，while()循環(huán)的執(zhí)行體要訪問N-1 次數(shù)組(當(dāng)最后一次到達(dá)根節(jié)點(diǎn)時，不執(zhí)行循環(huán)體)。共2N-1次。

? ? ? ? 3.由此可見，find(p)訪問數(shù)組的次數(shù)，是由觸點(diǎn)p對應(yīng)的節(jié)點(diǎn)在樹的高度所決定的。設(shè)p在樹的中的高度為h，則訪問數(shù)組的次數(shù)為2h+1次。

? ? ? ? 4.假設(shè)輸入的是有序整數(shù)對0-1、0-2、0-3…0-N，N-1對之后的N個觸點(diǎn)將全 部處于同一個連通分量內(nèi)(詳見main())，且由quick-union算法得到的樹的高度為N-1，其中0→1，1→2…N-1→N。

????????? 對于整數(shù)對0-i，執(zhí)行union(0,i)，將訪問2i+1次數(shù)組。

????????? ①其中0的根觸點(diǎn)是i-1，高度是i-1，根據(jù)3，find(0)訪問數(shù)組2i-1次

????????? ②其中i的根觸點(diǎn)是i，高度是0，根據(jù)3，find(i)訪問數(shù)組1次

????????? ③將i-1的根觸點(diǎn)(原指向本身，現(xiàn)指向觸點(diǎn)i)的數(shù)組內(nèi)容變成i，訪問數(shù)組1次

????????? PS：書上是2i+2次，我分析是0-i是連通的，這樣0的根觸點(diǎn)是i，i的根觸點(diǎn)是i，find(0)訪問2i+1次，find(i)訪問1次

????????????????? 共2i+2次。

????????????????? 可根據(jù)main()方法，此時0和i應(yīng)該不連通才對。

?????? 5.處理N對整數(shù)所需的所有find()操作訪問是；Σ(1→N)(2i) = 2(1+2+…N) ~N2

? ? ? ? ?可以看出quick-union和quick-find都是平方級別的算法。

?

轉(zhuǎn)載于:https://blog.51cto.com/youngcold/1106992

總結(jié)

以上是生活随笔為你收集整理的union-find算法分析(1)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。