天天看點
傳回

資料結構----并查集Java應用場景：Java實作及分析複雜度分析

并查集：(union-find sets)是一種簡單的用途廣泛的集合. 并查集是若幹個不相交集合，能夠實作較快的合并和判斷元素所在集合的操作，應用很多。

應用場景：

  • 網絡連接配接判斷：

    如果每個pair中的兩個整數分别代表一個網絡節點，那麼該pair就是用來表示這兩個節點是需要連通的。那麼為所有的pairs建立了動态連通圖後，就能夠盡可能少的減少布線的需要，因為已經連通的兩個節點會被直接忽略掉。

  • 變量名等同性(類似于指針的概念)：

    在程式中，可以聲明多個引用來指向同一對象，這個時候就可以通過為程式中聲明的引用和實際對象建立動态連通圖來判斷哪些引用實際上是指向同一對象。

換句話說就是，判斷兩個雙向節點是否連通，并且不需要給出路徑的問題，都可以用本資料結構快速解決。

Java實作及分析

并查集的api設計如下：

union(p,q); //合并p、q兩點使他們兩個連通.
find(p); //找到節點q的連通性,(處在什麼狀态合誰聯通)
isConnected(p,q);//通過find的api,我們可以找到兩個節點是否會連通的,即api

Quick-Find實作方式

分析以上的API，方法connected和union都依賴于find，connected對兩個參數調用兩次find方法，而union在真正執行union之前也需要判斷是否連通，這又是兩次調用find方法。是以我們需要把find方法的實作設計的盡可能的高效。是以就有了下面的Quick-Find實作。

/**
 * 簡單的數組并查集
 *      通過數組來維護區域是否連通，相同區域id的資料連通
 *      find時間複雜度為O(1)
 *      Union時間複雜度為O(n)
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS01 {
    //用一個數組來表示節點的連通性，有相同id内容的節點是連通的
    private int[] mIds;
    //節點個數
    private int mcount;

    /**
     * 初始化狀态，并設定每個節點互不連通
     * @param capcity
     */
    public UFS01(int capcity){
        mIds = new int[capcity];
        mcount = capcity;
        for (int i = ; i < capcity; i++) {
            mIds[i] = i;//各自節點的id都不一樣
        }
    }

    /**
     * 傳回目前節點的連通id
     * @param p
     * @return
     */
    public int find(int p){
        if (p< || p>=mcount){
            throw new RuntimeException("越界喽");
        }
        return mIds[p];
    }

    /**
     * 判斷a，b節點是否連通
     * @param a
     * @param b
     * @return
     */
    public boolean isConnect(int a, int b){
        return find(a)==find(b);
    }

    /**
     * 連通a，b節點
     *      聯合的整體思路:
     *          要麼把a索引在mIds中的狀态變成b的，
     *          要麼把b索引在mIds中的狀态變成a的
     * @param a
     * @param b
     */
    public void union(int a, int b){
        int aId = find(a);
        int bId = find(b);

        //如果已經連通，就不管了
        if (aId == bId){
            return;
        }

        //将bId的全部變成aId,需要将每個節點的id都變過來的
        for (int i = ; i < mIds.length; i++) {
            if (mIds[i] == bId){
                mIds[i] = aId;
            }
        }
    }
}

分析：

可以看到find方法是O(1)的複雜度，十分的快。但是union方法需要一次判斷每個節點的區域并改過來，調用一次就是O(n)，如果有m對相連的關系，時間複雜度小于O(nm)，也是O(n^2)級别的。

Quick-Union實作方式

上述方法為什麼會複雜度較高？每個節點的區域編号都是單獨記錄的，各自為政的，當需要修改的時候，就隻能一個一個去通知了。如果我們将節點有效地組織起來，友善查找和修改就好了，分析：連結清單、圖、樹什麼的，最後我們可以确定樹查找和修改效率好一點。

我們假設剛開始每個節點都是區域頭結點，即自己的父節點是自己。然後将相連的節點連接配接起來，每個節點最終都會指向一個區域頭節點，那就是他所在的區域。

/**
 * 類似樹的并查集
 *      通過指向父節點的指針來維護區域是否連通
 *      時間複雜度不定，如果組成了線性的樹，時間複雜度偏高。
 *
 *      可以改進的方向：維護每個節點的下面層數 或者 子節點 個數，union的時候，将個數少的節點連接配接到個數多的節點上面
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS02 {
    /**
     * 維護指向父節點的指針
     */
    private int[] mParents;
    private int mCount;

    /**
     * 初始化數組，預設每個節點都是區域頭節點，即指針指向自己
     * @param capacity
     */
    public UFS02(int capacity){
        mCount = capacity;
        mParents = new int[capacity];
        for (int i = ; i < capacity; i++) {
            mParents[i] = i;
        }
    }

    /**
     * 查找P節點的區域頭結點
     * @param p
     * @return
     */
    public int find(int p){
        if (p< || p>=mCount){
            throw new RuntimeException("越界喽");
        }
        /**
         * 向上查找，直到是一個區域頭結點
         */
        while (p != mParents[p]){
            p = mParents[p];
        }
        return p;
    }

    public boolean isConnect(int a, int b){
        return find(a)==find(b);
    }

    /**
     * 聯合，将a,b節點的區域頭結點聯合即可
     * @param a
     * @param b
     */
    public void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot){
            return;
        }
        mParents[bRoot] = aRoot;
    }
}

分析：

當然，用樹結構的話就得小心，如果樹結構退化成了連結清單怎麼辦，那豈不是效率也挺低？當然，我們可以用紅黑樹，AVL樹等，我們此處稍加分析，可以發現，union的時候稍加判斷，可以提高效率啊：可以改進的方向，維護每個節點的下面層數 或者 子節點 個數，union的時候，将個數少的節點連接配接到個數多的節點上面。

Weighted Quick-Union 實作方式

如上所說，維護每個節點的下面層數 或者 子節點 個數，union的時候，将個數少的節點連接配接到個數多的節點上面。

/**
 * 可以改進的方向：維護每個節點的子節點 個數，union的時候，将個數少的節點連接配接到個數多的節點上面
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS04 {
    private int[] mParents;
    //新加一個數組用來記錄每一個節點,以它為根的元素的個數。
    //mSize[i]表示以i為根的樹結構中的元素個數。
    private int[] mSize;
    private int mCount;

    public UFS04(int capacity){
        mCount = capacity;
        mParents = new int[mCount];
        mSize = new int[mCount];
        for (int i = ; i < mCount; i++) {
            mParents[i] = i;
            //預設每個都是1：獨立的時候含有一個元素.
            mSize[i] = ;
        }
    }
    //以下find和isConnected都用不到mSize.
    public int find(int p){
        if( p< || p>=mCount){
            //...做一些異常處理
        }
        while(p!=mParents[p]){
            p = mParents[p];
        }
        return p;
    }
    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }
    //聯合的時候就需要用到mSize了.看看那個節點為根的樹形集合中元素多，
    //然後把少的那個節點對應的根，指向多的那個節點對應的根。
    public void union(int p,int q){
        //前兩步不變
        int pRoot= find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        int pSize = mSize[pRoot];//初始事都是根，為1
        int qSize = mSize[qRoot];
        //如果pRoot為根的樹形集合含有的元素比qRoot的多
        if(pSize > qSize){
            //注意是少的索引的父節點指向多的
            mParents[qRoot] = pRoot;
            //注意此時mSize的改變,由于qRoot歸并到了pRoot當中那麼
            //需要加上相應數量的size，注意qRoot對應的size并沒有改變
            mSize[pRoot] = pSize+qSize;
        }/*else if(pSize < qSize){//同理
            mParents[pRoot] = qRoot;
            mSize[qRoot] = pSize+qSize;
        }else{//如果兩個相等那麼就無所謂了，誰先合并到誰都可以.
            mParents[qRoot] = pRoot;
            mSize[pRoot] = pSize+qSize;
        }*/
        //然後就可以把等于的合入到大于或者小于的裡面.
        else{//此處把小于和等于合到一塊
            mParents[pRoot] = qRoot;
            mSize[qRoot] = pSize+qSize;
        }
    }
}
           
/**
 * 可以改進的方向：維護每個節點的下面層數，union的時候，将個數少的節點連接配接到個數多的節點上面
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS05 {
    private int[] mParents;
    //mRank[i]表示以i為根節點的集合所表示的樹的層數
    private int[] mRank;
    private int mCount;
    public UFS05(int capacity){
        mCount = capacity;
        mParents = new int[mCount];
        mRank = new int[mCount];
        for (int i = ; i < mCount; i++) {
            mParents[i] = i;
            //預設每個都是1：表示深度為1層
            mRank[i] = ;
        }
    }
    //以下find和isConnected都用不到mRank.
    public int find(int p){
        if( p< || p>=mCount){
            //...做一些異常處理
        }
        while(p!=mParents[p]){
            p = mParents[p];
        }
        return p;
    }
    public boolean isConnected(int p,int q){
        return find(p)==find(q);
    }
    //找到p、q節點所在的樹形集合的根節點，它的深度。然後把深度小的根節點合入到深度大的根節點當中
    public void union(int p,int q){
        //前兩步不變
        int pRoot= find(p);
        int qRoot = find(q);
        if(pRoot == qRoot){
            return;
        }
        int pRank = mRank[pRoot];//初始事都是深度為1
        int qRank= mRank[qRoot];
        //如果p的深度比q的深度大.
        if(pRank > qRank){
            //注意是小的指向大的,也就是為小的重新讀之
            mParents[qRoot] = pRoot;
            //此時把并不需要維護pRank,因為qRank是比pRank小的
            //也就是q更淺，它不會增加p的深度，隻會增加去p的寬度
        }else if(pRank < qRank){
            mParents[pRoot] = qRoot;
            //同樣的道理不需要維護qRank,p隻會增加它的寬度
        }else{
            //當兩個深度相同的時候,誰指向誰都可以，但是注意此時的深度維護
            //被指向的那個的深度需要加1.
            //此時讓qRoot指向pRoot吧.
            mParents[qRoot] = pRoot;
            mRank[pRoot]++;
        }
    }
}

分析：

權重之後，樹的高度可以大幅下降，find方法的效率就更高了，運作效率也提升了。

Weighted Quick-Union With Path Compression實作方式

我們來想一個更狠的，如果将樹弄得特别扁平，隻有 區域節點-其他節點 兩層怎麼樣？

隻需在每次find的時候，将第二層下面的節點指向上層的上層，多次find之後，就是一個二層樹了。

/**
        帶路徑壓縮的并查集
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS06 {
    /**
     * 維護指向父節點的指針
     */
    private int[] mParents;
    private int mCount;

    /**
     * 初始化數組，預設每個節點都是區域頭節點，即指針指向自己
     * @param capacity
     */
    public UFS06(int capacity){
        mCount = capacity;
        mParents = new int[capacity];
        for (int i = ; i < capacity; i++) {
            mParents[i] = i;
        }
    }

    /**
     * 查找P節點的區域頭結點
     * @param p
     * @return
     */
    public int find(int p){
        if (p< || p>=mCount){
            throw new RuntimeException("越界喽");
        }
        while (p != mParents[p])
        {
            // 将p節點的父節點設定為它的爺爺節點
            mParents[p] = mParents[mParents[p]];
            p = mParents[p];
        }
        return p;
    }

    public boolean isConnect(int a, int b){
        return find(a)==find(b);
    }

    /**
     * 聯合，将a,b節點的區域頭結點聯合即可
     * @param a
     * @param b
     */
    public void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot){
            return;
        }
        mParents[bRoot] = aRoot;
    }
}

複雜度分析

Algorithm Union Find
Quick-Find N 1
Quick-Union Tree height Tree height
Weighted Quick-Union lgN lgN
Weighted Quick-Union With Path Compression Very near to 1 (amortized) Very near to 1 (amortized)
算法 java 資料結構 并查集
上一篇: 線上富文本編輯器 - Xproer-松鼠
下一篇: 【開源我寫的富文本】打造全網最勁富文本系列之技術選型

繼續閱讀