無向圖的處理算法（四）連通分量

asce1885 發布于2019-08-14 12:10 / 3499人閱讀

這篇講的是連通分量，連通分量是深度優先搜索算法的一個應用。
每進行了一次dfs，就會找到一條連通分量。
定義如下的API

public class CC
    CC(Graph g)      預處理構造函數
    boolean connected(int v,in w)  v和w連通嗎
    int count()     改圖中的連通分量個數
    int id(int v)   頂點v所在的連通分量編號

具體實現如下：

package Graph;

public class CC {
    /*
     * 計算一個圖中的連通分量，從起始點開始進行dfs算法，同時用一個以頂點作為索引的數組id[]來保存該點所在的連通分量的起始點，也就是id
     * 這樣，判斷兩個點是否處于同一個連通分量，只要判斷id是否相同
     */
    private boolean[] marked;
    private int[] id;
    private int count;

    public CC(Graph G){
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for(int s = 0;s < G.V();s++){
            if(!marked[s]){
                dfs(G,s);
                count++;
            }
        }
    }
    private void dfs(Graph G,int v){
        marked[v] = true;
        id[v] = count;          //該連通分量的起始節點
        for(int w:G.adj(v)){
            if(!marked[w])
                dfs(G,w);
        }
    }

    public boolean connected(int v,int w){
        return id[v] == id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return count;
    }
}

同樣還能解決雙色問題，即“能夠用兩種不同顏色將頂點著色，使得相鄰的頂點顏色不同嗎？等價于這個圖是一個二分圖嗎？

/*
 * 使用dfs算法，來判斷一個圖中的頂點是否可以用兩種顏色染色，使得相鄰的頂點顏色不同
 * 也就是，判斷該圖是否是一個二分圖：
 * 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。
 * 
 */
public class TwoColor {
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable = true;

    public TwoColor(Graph G){
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for(int s = 0;s < G.V();s++){
            if(!marked[s])
                dfs(G,s);
        }
    }

    private void dfs(Graph G,int v){
        marked[v] = true;
        for(int w: G.adj(v)){
            if(!marked[w]){
                color[w] =!color[v];
            }
            else if (color[w] == color[v])
                isTwoColorable = false;
        }
    }
    public boolean isTwoColorable(){
        return isTwoColorable;
    }
}

GPU云服務器云服務器最大連通區域算法java 最大連通子圖算法 webrtc agc算法四字符串處理算法匹配算法

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

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

算法第四版4.1-無向圖詳解

摘要：樹是一副無環連通圖。互不相連的樹組成的集合稱為森林。表示無向圖的數據類型圖的基本操作的兩個構造，得到頂點數和邊數，增加一條邊。該方法不符合第一個條件，上百萬個頂點的圖是很常見的空間不滿足。四種重要的圖模型：無向圖（簡單連接）有向圖（連接有方向性）加權圖（連接帶有權值）加權有向圖（連接既有方向性又帶有權值）無向圖定義：由一組頂點和一組能夠將兩個頂點相連的邊組成。特殊：...

scola666 2019-08-14 17:53 評論0 收藏0
算法（第4版） Chapter 4.1 無向圖

摘要：邊僅由兩個頂點連接，并且沒有方向的圖稱為無向圖。用分隔符當前為空格，也可以是分號等分隔。深度優先算法最簡搜索起點構造函數找到與起點連通的其他頂點。路徑構造函數接收一個頂點，計算到與連通的每個頂點之間的路徑。 Algorithms Fourth EditionWritten By Robert Sedgewick & Kevin WayneTranslated By 謝路云Chapter...

kamushin233 2019-08-14 17:14 評論0 收藏0
算法（第4版） Chapter 4.2 強聯通性 Tarjan算法補充

摘要：在實際的測試中，算法的運行效率也比算法高左右。此外，該算法與求無向圖的雙連通分量割點橋的算法也有著很深的聯系。學習該算法，也有助于深入理解求雙連通分量的算法，兩者可以類比組合理解。固屬于同一連通分支。參考資料http://blog.csdn.net/acmmmm/a...https://www.byvoid.com/blog/s...http://blog.csdn.net/noth...

maybe_009 2019-08-14 17:13 評論0 收藏0
算法之不定期更新（三）（2018-04-24）

摘要：實現這個想法之后就發現，時間復雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級，還有好多已經說爛了的題就不分享了。如果有什么意見或者想法歡迎在評論區和我交流題目 input: n // 代表無向圖的頂點數 // 從1開始 m // 無向圖的邊數 arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點0和頂點2相連，頂點3和頂點4相連） ...

darryrzhong 2019-08-22 16:40 評論0 收藏0