国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

快速理解Union Find算法--java代碼實(shí)現(xiàn)

seanlook / 1311人閱讀

摘要：在這個方法里，查找連通分量的標(biāo)識只需要的時(shí)間復(fù)雜度，但是將兩個分量連接起來卻需要遍歷整個數(shù)組，因此時(shí)間復(fù)雜度為。

什么是Union Find

Union Find是并查集的一種數(shù)據(jù)結(jié)構(gòu)。 先理解兩個對象之間“相連的關(guān)系”
對象p和對象q相連是指：

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

在并查集中，如果想要將連個對象相連，當(dāng)且僅當(dāng)這兩個對象不在同一個連通分量中時(shí)，才會相連。這句話什么意思呢？也就是說，如果已經(jīng)存在一條路徑，使得p和q之間相通，那么就不會對后續(xù)的連接p和q的請求作出任何操作。

Union Find API

并查集需要的對外接口如下。在這里我們默認(rèn)初始化時(shí)知道并查集中對象的個數(shù)并且不允許后續(xù)添加新的對象進(jìn)來

UnionFind(int N) : 初始化并查集，并查集中包含N個互不相連的對象
void union(int p, int q) : 連接p,q
int find(int p) : p所在的連通分量的標(biāo)識符
boolean connect(int p, int q) : 如果p和q存在于同一個分量中則返回true
int count() : 連通分量的數(shù)量
UnionFind基本設(shè)計(jì)

在這里，我們使用長度為N的整數(shù)數(shù)組來表示一個并查集的數(shù)據(jù)結(jié)構(gòu)，其中下標(biāo)為i的元素的值是指i對象對應(yīng)的連通分量的標(biāo)識。

    public class UnionFind{
        int[] id;
        int count;
        
        public UnionFind(int N){
        
        }
        public int count(){
            return count;
        }
        
        public boolean connected(int p, int q){
            return find(p) == find(q);
        }
        
        public int find(int p){
            //后面實(shí)現(xiàn)
        }
        
        public int union(int p, int q){
            //后面實(shí)現(xiàn)
        }
    }
方法一：quick find

如何證明兩個對象是連通的呢？只要id[p]和id[q]對應(yīng)的連通分量標(biāo)識是相同的，那么p和q一定是連通的。
那么如果想要連通p和q的話，只需要將q的所有標(biāo)識更新為p的標(biāo)識就行了。

    public int find(int p){
        return id[p];
    }
    
    public void union(int p, int q){
        int pId = find(p);
        int qId = find(q);
        if(pId == qId) return;
        for(int i = 0 ; i

在這個方法里，查找連通分量的標(biāo)識只需要O(1)的時(shí)間復(fù)雜度，但是將兩個分量連接起來卻需要遍歷整個數(shù)組，因此時(shí)間復(fù)雜度為O(n)。如果數(shù)組很大的話，連接操作將需要大量的時(shí)間。

方法二：quick union

為了改進(jìn)方法一對大容量觸點(diǎn)過慢的情況，改進(jìn)了連接操作。在這個方法里，所有的連通分量的視圖是一棵樹，如果將兩個分量相連，那么可以將其中一個連通分量的根直接連接到另一個連通分量的根節(jié)點(diǎn)上。


    public int find(int p){
        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;
        id[p] = qRoot;
        count--;
    }

方法三：weighted quick union

在上一種方法中，如果從邏輯視角，也就是樹的視角查看這個連通分量的話，我們可以預(yù)想到一些極端情況，比如這棵樹最終成了一個鏈表的形狀。那么每一次查找樹的根節(jié)點(diǎn)都意味著需要遍歷這棵樹的所有節(jié)點(diǎn)，時(shí)間復(fù)雜度顯著提升。那么如何才能避免這種極端情況的出現(xiàn)呢？我們可以根據(jù)需要連通的兩個對象的樹的元素個數(shù)來決定將哪個樹的根作為新的樹的根。這里我們使用一個新的數(shù)據(jù)結(jié)構(gòu)int[] size存儲各個根節(jié)點(diǎn)對應(yīng)的分量的大小。初始化時(shí)所有的分量的大小都為1。


    public int find(int p){
        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;
        if(size(pRoot) > size(qRoot)) {id[qRoot] = pRoot; size[pRoot] += size[qRoot];}
        else {id[pRoot] = qRoot; size[qRoot] += size[pRoot];}
        count--;
    }


這樣就可以避免極端樹的存在

Refrences

算法-圖靈出版社



想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/70745.html

相關(guān)文章

  • Union-Find并查集算法學(xué)習(xí)筆記

    摘要：算法鏈接學(xué)習(xí)工具，，環(huán)境搭建在小伙伴的推薦下，這個學(xué)期開始上普林斯頓的算法課。一系列的整數(shù)對代表與相互連接，比如等，每一個整數(shù)代表了一個。我覺得這個可能也是并查集相關(guān)應(yīng)用。這學(xué)期繼續(xù)學(xué)習(xí)深入理解了就能明白了。 《算法》鏈接：1.5 Case Study: Union-Find學(xué)習(xí)工具：mac，java8，eclipse,coursera 環(huán)境搭建在小伙伴的推薦下，這個學(xué)期開始上普林斯頓...

    hzc 評論0 收藏0

  • 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn)

    摘要：算法第一章學(xué)習(xí)筆記實(shí)現(xiàn)更多內(nèi)容目標(biāo)總結(jié)本書主要內(nèi)容，相應(yīng)算法使用來模仿實(shí)現(xiàn)在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限確定有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn) 更多內(nèi)容 目標(biāo)：總結(jié)本書主要內(nèi)容，相應(yīng)算法使用js來模仿實(shí)現(xiàn) 在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。我們關(guān)注的大多...

    baishancloud 評論0 收藏0

  • 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn)

    摘要：算法第一章學(xué)習(xí)筆記實(shí)現(xiàn)更多內(nèi)容目標(biāo)總結(jié)本書主要內(nèi)容，相應(yīng)算法使用來模仿實(shí)現(xiàn)在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限確定有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn) 更多內(nèi)容 目標(biāo)：總結(jié)本書主要內(nèi)容，相應(yīng)算法使用js來模仿實(shí)現(xiàn) 在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。我們關(guān)注的大多...

    K_B_Z 評論0 收藏0

  • 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn)

    摘要：算法第一章學(xué)習(xí)筆記實(shí)現(xiàn)更多內(nèi)容目標(biāo)總結(jié)本書主要內(nèi)容，相應(yīng)算法使用來模仿實(shí)現(xiàn)在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限確定有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。 《算法》第一章學(xué)習(xí)筆記js實(shí)現(xiàn) 更多內(nèi)容 目標(biāo)：總結(jié)本書主要內(nèi)容，相應(yīng)算法使用js來模仿實(shí)現(xiàn) 在計(jì)算機(jī)科學(xué)領(lǐng)域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計(jì)算機(jī)程序來實(shí)現(xiàn)的解決問題的方法。我們關(guān)注的大多...

    qingshanli1988 評論0 收藏0

  • 用并查集(find-union)實(shí)現(xiàn)迷宮算法以及最短路徑求解

    摘要：本人郵箱歡迎轉(zhuǎn)載轉(zhuǎn)載請注明網(wǎng)址代碼已經(jīng)全部托管有需要的同學(xué)自行下載引言迷宮對于大家都不會陌生那么迷宮是怎么生成已經(jīng)迷宮要如何找到正確的路徑呢用代碼又怎么實(shí)現(xiàn)帶著這些問題我們繼續(xù)往下看并查集朋友圈有一種算法就做并查集什么意思呢比如現(xiàn)在有零 本人郵箱: 歡迎轉(zhuǎn)載,轉(zhuǎn)載請注明網(wǎng)址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

    xiangchaobin 評論0 收藏0

發(fā)表評論

0條評論

seanlook

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<