快速理解Union Find算法--java代碼實現

seanlook 發布于2019-08-16 10:56 / 1319人閱讀

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

什么是Union Find

Union Find是并查集的一種數據結構。先理解兩個對象之間“相連的關系”
對象p和對象q相連是指：

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

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

Union Find API

并查集需要的對外接口如下。在這里我們默認初始化時知道并查集中對象的個數并且不允許后續添加新的對象進來

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

UnionFind基本設計

在這里，我們使用長度為N的整數數組來表示一個并查集的數據結構，其中下標為i的元素的值是指i對象對應的連通分量的標識。

    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){
            //后面實現
        }
        
        public int union(int p, int q){
            //后面實現
        }
    }

方法一：quick find

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

    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
在這個方法里，查找連通分量的標識只需要O(1)的時間復雜度，但是將兩個分量連接起來卻需要遍歷整個數組，因此時間復雜度為O(n)。如果數組很大的話，連接操作將需要大量的時間。
方法二：quick union
為了改進方法一對大容量觸點過慢的情況，改進了連接操作。在這個方法里，所有的連通分量的視圖是一棵樹，如果將兩個分量相連，那么可以將其中一個連通分量的根直接連接到另一個連通分量的根節點上。
    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
在上一種方法中，如果從邏輯視角，也就是樹的視角查看這個連通分量的話，我們可以預想到一些極端情況，比如這棵樹最終成了一個鏈表的形狀。那么每一次查找樹的根節點都意味著需要遍歷這棵樹的所有節點，時間復雜度顯著提升。那么如何才能避免這種極端情況的出現呢？我們可以根據需要連通的兩個對象的樹的元素個數來決定將哪個樹的根作為新的樹的根。這里我們使用一個新的數據結構int[] size存儲各個根節點對應的分量的大小。初始化時所有的分量的大小都為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
算法-圖靈出版社

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 union-find 圖像識別算法實現代碼 java實現離群算法 java遺傳算法實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/70745.html

Union-Find并查集算法學習筆記

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

hzc 2019-08-14 17:08 評論0 收藏0
《算法》第一章學習筆記js實現

摘要：算法第一章學習筆記實現更多內容目標總結本書主要內容，相應算法使用來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限確定有效的并適合用計算機程序來實現的解決問題的方法。《算法》第一章學習筆記js實現更多內容目標：總結本書主要內容，相應算法使用js來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計算機程序來實現的解決問題的方法。我們關注的大多...

baishancloud 2019-08-30 13:45 評論0 收藏0
《算法》第一章學習筆記js實現

摘要：算法第一章學習筆記實現更多內容目標總結本書主要內容，相應算法使用來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限確定有效的并適合用計算機程序來實現的解決問題的方法。《算法》第一章學習筆記js實現更多內容目標：總結本書主要內容，相應算法使用js來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計算機程序來實現的解決問題的方法。我們關注的大多...

K_B_Z 2019-08-21 17:05 評論0 收藏0
《算法》第一章學習筆記js實現

摘要：算法第一章學習筆記實現更多內容目標總結本書主要內容，相應算法使用來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限確定有效的并適合用計算機程序來實現的解決問題的方法。《算法》第一章學習筆記js實現更多內容目標：總結本書主要內容，相應算法使用js來模仿實現在計算機科學領域，我們用算法這個詞來描述一種有限、確定、有效的并適合用計算機程序來實現的解決問題的方法。我們關注的大多...

qingshanli1988 2019-08-01 17:47 評論0 收藏0
用并查集(find-union)實現迷宮算法以及最短路徑求解

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

xiangchaobin 2019-08-16 10:30 評論0 收藏0