2.3.weighted-quick-union——加權(quán)quick-union算法

上篇的quick-union算法的效率之所以低(平方級(jí)別)，最主要的原因是union(p,q)方法，隨意將一棵樹連接到另一棵樹上(一棵樹對(duì)應(yīng)一個(gè)連通分量)。

1.如果是小樹(高度低)連接到大樹的根節(jié)點(diǎn)(高度高)，則小樹的高度加1，而整個(gè)樹的高度不變。

2.如果是大樹(高度高)連接到小樹的根節(jié)點(diǎn)(高度低)，則大樹的高度加1，而整個(gè)樹的高度由原來的小樹高度變成大樹高度加1。

根據(jù)quick-union算法分析，find(p)訪問的數(shù)組的次數(shù)與節(jié)點(diǎn)p所在的高度有關(guān)。高度越高，訪問數(shù)組的次數(shù)越多。

由此可見，為了減少訪問數(shù)組的次數(shù)，提高算法效率，在執(zhí)行union(p,q)操作時(shí)，確保是情況1，即小樹連接到大樹上。為此，需要一個(gè)數(shù)組sz[]來記錄觸點(diǎn)p所在的連通分量含有的觸點(diǎn)(觸點(diǎn)越多，對(duì)應(yīng)的樹的節(jié)點(diǎn)越多，即為大樹)。

3.當(dāng)然還有一種特殊情況，即p和q所在的連通分量對(duì)應(yīng)的樹高度相等，此時(shí)無論是p連接到q還是q連接到p，樹的高度都會(huì)增加。在加權(quán)quick-union算法中，這是最壞的情況。

因此，由加權(quán)quick-union構(gòu)成的樹的高度將遠(yuǎn)小于未加權(quán)所構(gòu)造的樹的高度。

1: public class WeightedQuickUnionUF extends QuickUnionUF { 2:? 3: /** 4: * sz[p]表示觸點(diǎn)p所在的連通分量所含的觸點(diǎn)數(shù) 5: */ 6: private int[] sz; 7:? 8: public WeightedQuickUnionUF(int N) { 9: super(N); 10: // TODO Auto-generated constructor stub 11: sz = new int[N]; 12: for (int i = 0; i < N; i++) 13: sz[i] = 1;// 初始化時(shí)，每個(gè)觸點(diǎn)都是一個(gè)連通分量 14: } 15:? 16:? 17: @Override 18: public void union(int p, int q) { 19: // TODO Auto-generated method stub 20: int pRoot = find(p); 21: int qRoot = find(q); 22: 23: if(pRoot == qRoot) 24: return; 25: 26: if(sz[pRoot] < sz[qRoot]){//當(dāng)觸點(diǎn)p所在的連通分量對(duì)應(yīng)的樹是小樹，則連接到q的連通分量上去 27: id[pRoot] = qRoot; 28: sz[qRoot] += sz[pRoot];//不要忘了，被連接的樹包含的節(jié)點(diǎn)數(shù)要相應(yīng)的增加 29: }else{//當(dāng)觸點(diǎn)p所在的連通分量對(duì)應(yīng)的樹是大樹，則q所在的連通分量連接到p的連通分量上去 30: id[qRoot] = pRoot; 31: sz[pRoot] += sz[qRoot]; 32: } 33: 34: count -- ; 35: } 36: 37: public static void main(String[] args) { 38: DirectInput.directInput(args); 39: int N = StdIn.readInt(); 40: UF uf = new WeightedQuickUnionUF(N); 41: for(int i=0;i<N;i++){ 42: int p = StdIn.readInt(); 43: int q = StdIn.readInt(); 44: 45: if(uf.connected(p, q)) continue; 46: 47: uf.union(p, q); 48: StdOut.println(p + " " + q); 49: } 50: StdOut.println(uf.count() + " components"); 51: } 52:? 53: }

?

測試結(jié)果

算法分析

1.最壞的情況：將要被歸并的樹的大小總是相等的(且總是2^n)。每個(gè)樹均是含有2^n節(jié)點(diǎn)的滿二叉樹，因此高度正好是n。當(dāng)歸并兩個(gè)含有2^n節(jié)點(diǎn)的樹時(shí)，得到含有2^(n+1)個(gè)節(jié)點(diǎn)的書，由此樹的高度增加到n+1。由此可知，加權(quán)quick-union算法是對(duì)數(shù)級(jí)別的。即對(duì)于N個(gè)觸點(diǎn)所構(gòu)成的樹最高的高度為lgN。

2.情況1的最壞的情況是怎么得來的？

簡單的分析可知，加權(quán)quick-union算法不可能會(huì)得到線性表(未加權(quán)的quick-union會(huì)產(chǎn)生退化成線性表的樹)。因此，每層的節(jié)點(diǎn)越多，樹的高度就越小。最壞的情況就是滿二叉樹。

3.加權(quán)quick-union算法處理N個(gè)觸點(diǎn)，M條連接時(shí)最多訪問數(shù)組cMlgN次。(c為常數(shù)。每處理一條連接，調(diào)用一次union(p,q)方法。而union(p,q)是lgN級(jí)別的。lg[height(p)] + lg[height(q)] + 5 = clgN，M次即為cMlgN)。而quick-find算法以及某些情況下未加權(quán)的quick-union算法至少訪問數(shù)組MN次。

?

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

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

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

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