找無向圖的連通分量

使用深度優先搜索可以很簡單地找出一幅圖的所有連通分量，回憶連通圖的概念：如果從任意頂點都存在一條路徑達到任意一個頂點，則稱這幅圖是連通圖。而連通分量指的是一幅圖中所有極大連通子圖。將整幅圖比喻成串了珠子的繩子的話，將任意頂點提起，連通圖將是一個整體;非連通圖散成若干條較小的整體，這每一條整體就是一個整幅圖的一個連通分量。易知連通圖只有一個連通分量，就是它自身;如果一幅圖的頂點都是分散的，那么連通分量的個數(只有一個頂點)就是圖的頂點數個。所以連通分量的數量范圍為[1, graph.vertexNum]

[[209930]]

下面這幅圖，有3個連通分量。

回憶深度優先搜索的過程：它從某個頂點出發，訪問它的某一個鄰接點，接著訪問這個鄰接點的某一個鄰接點….如此深入下去，一直到達某個頂點發現周圍的鄰接點都已經訪問過了，此時往回退到上一個頂點，訪問該頂點的未被訪問過的鄰接點…直到所有頂點都被訪問過。很容易知道，在一次深度優先遍歷中所有訪問過的頂點都是互相可達的，或者說是連通的。我們按照Union-Find算法那樣，給每個連通分量標示一個id，即擁有同一個id的頂點歸屬于同一個連通分量。上面已經分析過，連通分量的數量范圍為[1, graph.vertexNum]，所以需要的id個數graph.vertexNum就足夠，存儲id的數組int[] id的范圍是[0, graph.vertexNum – 1]。

下面是尋找無向圖的所有連通分量的代碼，所用的無向圖就是上面那副有3個連通分量的圖。

package Chap7; 
 
import java.util.LinkedList; 
 
public class CC { 
    // 用來標記已經訪問過的頂點，保證每個頂點值訪問一次 
    private boolean[] marked; 
    // 為每個連通分量標示一個id 
    private int[] id; 
    // 連通分量的個數 
    private int count; 
 
    public CC(UndiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        id = new int[graph.vertexNum()]; 
        for (int s = 0; s < graph.vertexNum(); s++) { 
            if (!marked[s]) { 
                dfs(graph, s); 
                // 一次dfs調用就是一個連通分量，第一個連通分量id為0。 
                // 之后分配的id要自增，第二個連通分量的id為1，以此類推 
                count++; 
            } 
        } 
    } 
 
    private void dfs(UndiGraph<?> graph, int v) { 
        // 將剛訪問到的頂點設置標志 
        marked[v] = true; 
        id[v] = count; 
        // 從v的所有鄰接點中選擇一個沒有被訪問過的頂點 
        for (int w : graph.adj(v)) { 
            if (!marked[w]) { 
                dfs(graph, 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; 
    } 
 
    public static void main(String[] args) { 
        // 邊 
        int[][] edges = {{0, 6}, {0, 2}, {0, 1}, {0, 5}, 
                {3, 4}, {3, 5}, {4, 5}, {4, 6}, {7, 8}, 
                {9, 10}, {9, 11}, {9, 12}, {11, 12}}; 
 
        UndiGraph<?> graph = new UndiGraph<>(13, edges); 
        CC cc = new CC(graph); 
        // M是連通分量的個數 
        int M = cc.count(); 
        System.out.println(M + "個連通分量"); 
        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M]; 
        for (int i = 0; i < M; i++) { 
            components[i] = new LinkedList<>(); 
        } 
        // 將同一個id的頂點歸屬到同一個鏈表中 
        for (int v = 0; v < graph.vertexNum(); v++) { 
            components[cc.id(v)].add(v); 
        } 
        // 打印每個連通分量中的頂點 
        for (int i = 0; i < M; i++) { 
            for (int v : components[i]) { 
                System.out.print(v+ " "); 
            } 
            System.out.println(); 
        } 
    } 
 
} 

程序將打印如下信息

3個連通分量 
0 1 2 3 4 5 6  
7 8  
9 10 11 12  

對比上圖，吻合!

深度優先搜索的應用——判斷無向圖是否有環

使用DFS可以很方便地判斷一幅無向圖是否成環(假設不存在自環和平行邊)。

package Chap7; 
 
public class UndirectCycle { 
    private boolean marked[]; 
    private boolean hasCycle; 
 
    public UndirectCycle(UndiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        for (int s = 0; s < graph.vertexNum(); s++) { 
            if (!marked[s]) { 
               // 剛開始沒有頂點被訪問過，所以當前正訪問和上一個被訪問的頂點設置為起點s。當dfs被遞歸調用一次后，當前正訪問的參數v是s的一個鄰接點，而上一個被訪問的參數u是s，符合 
                dfs(graph, s, s); 
            } 
        } 
    } 
    // 修改過的DFS，v表示當前正訪問的頂點，u表示上一個訪問的頂點 
    private void dfs(UndiGraph<?> graph, int v, int u) { 
        // 將剛訪問到的頂點設置標志 
        marked[v] = true; 
        // 從v的所有鄰接點中選擇一個沒有被訪問過的頂點 
        for (int w : graph.adj(v)) { 
            if (!marked[w]) { 
                dfs(graph, w, v); 
            } else if (w != u) { 
                hasCycle = true; 
            } 
        } 
    } 
 
    public boolean hasCycle() { 
        return hasCycle; 
    } 
} 

稍微修改了下DFS算法，新增了一個參數u，表示上一個被訪問的頂點。判斷是否有環，關鍵就是那句else if (w != u)。注意是w和u比較。為什么這樣就能判斷有環了呢?如果當前訪問的頂點v的這個鄰接點w是之前已經訪問過的，且不是上一個訪問的頂點，那么該無向圖就有環。也就是下圖這種情況。

w已經被訪問過且w == u的情況，無環。也就是下圖的情況

尋找有向圖的強連通分量

在一幅有向圖中，如果兩個頂點v和w是互相可達的，則稱它們是強連通的。如果一幅有向圖中任意兩個頂點都是強連通的，那么這幅圖也是強連通的。

有向環和強連通有著緊密的關系，兩個頂點是強連通的當且僅當它們都在一個普通的有向環中。這很容易理解，存在v -> w的路徑，也存在w -> v的路徑，則v和w是強連通的，同時也說明了這是一個環結構。一個含有V個頂點的有向圖，含有的強連通分量的個數范圍為[1, V]——強連通圖只有一個強連通分量，而一個有向無環圖中則含有V個強連通分量。

下圖中就含有5個強連通分量。

和計算無向圖中的連通分量一樣，計算有向圖的強連通分量也是深度優先搜索的一個應用。只需在上面代碼的基礎上加上幾行，即可實現這個稱為Kosaraju的算法。

這個算法雖然實現簡單，但是并不好理解。nullzx的博客園這篇博文講得很好，看完后算是理解了Kosaraju算法那神奇的做法…

上圖是一個含有兩個強連通分量的有向圖。強連通分量和強連通分量之間不會形成環，否則這兩個連通分量就是一個整體，即看成同一個強連通分量。如果將連通分量縮小成一個頂點，那么上圖就是一個含有兩個頂點的無環圖，且左邊的頂點指向了右邊的頂點。

如果從左邊的強連通分量中任意一個頂點開始DFS，那么只需一次調用就能訪問到圖中所有頂點，這主要是因為兩個連通分量之間A2指向B3;相反，從右邊的強連通分量中任意一個頂點出發深度優先搜索，需要調用DFS兩次——這正好是強連通分量的個數，而且每一次調用DFS訪問的頂點就是一個強連通分量中的所有頂點(先假設這句話是正確的，下面會給出這個命題的證明)，比如第一次調用DFS，訪問了B3、B4、B5，這三個頂點恰好組成右邊強連通分量的所有頂點。反過來想，為了找出全部的強連通分量，保證DFS訪問頂點的順序為B強連通分量中任意一個頂點在A強連通分量全部頂點之前即可。或者換個角度思考，將連通分量縮小成頂點后，整個圖變成了無環圖，DFS訪問頂點的順序是：先訪問那些不指向任何連通分量(頂點)的頂點，比如上面A2指向B3，所以應該先訪問B中的頂點。說得更通俗點也就是，DFS將先訪問出度為0的那些連通分量(看成一個頂點)，這樣能保證一次調用DFS肯定是在同一個連通分量里面遞歸，不會跑到其他連通分量中取。如果先訪問那些指向了其他分量(出度不為0)的分量，DFS一定能進入到其他連通分量中，如A連通分量通過A2進入到B連通分量中，這樣的話，一次DFS遍歷了多個強連通分量，根本就達不到目的。

如B3, A2, A0, A1, B4, B5，按照這個序列調用DFS，就能保證DFS一定會被調用兩次。當然序列是不唯一的，在DFS中有一種常見的序列可以保證這種關系，即逆后序。

所謂逆后序就是在DFS遞歸調用返回之前，將該頂點壓入棧中得到的序列。例如dfs(s) -> dfs(v)這個遞歸調用棧，表示了一條s -> v的路徑，v將比s先返回，故先存入v，再存入s，棧中的順序是sv。

現在可以說說Kosaraju算法的思路：

• 將原圖取反。
• 對反向圖作深度優先遍歷，得到頂點的逆后序排列。
• 回到原圖，按照上面得到的逆后序序列的順序，對原圖進行深度優先搜索。(而不是按照0, 1, 2…這樣的頂點順序)

我們來看，為什么反向圖的逆后序就是我們需要的序列。

上圖是取反后的有向圖。設原圖為G，取反后的圖為Gr。深度優先搜索Gr有兩種可能：

• 從強連通分量A中任意一個頂點開始，需要調用兩次DFS，第一次A0、A1、A2入棧;第二次B3、B4、B5入棧。這種情況下，強連通分量B所有頂點都在強連通分量A之前。
• 從強連通分量B中的任意一個頂點開始，只需調用一個DFS即可遍歷到所有頂點。由于是逆后序，因為B中最先被訪問的頂點，最后才會返回，因此它在棧中位于棧頂的位置。

上面兩種情況都保證了B中至少有一個頂點在A全部頂點之前，回到原圖中就會先對B中的頂點先進行DFS。推廣到擁有多個強連通分量的有向圖，上述推論依然是成立的。

反向圖的逆后序實際上是它的一個偽拓補序列(“偽”是因為可能有環結構)，將連通分量縮小成一個頂點后，有向圖無環了，反向圖的逆后序就成了一個拓補序列——入度為0的頂點的總是排在前面。則在原圖中，該拓補序列就變成了出度為0的頂點排在前面了，上面有分析到，對那些出度為0的分量(已看作頂點)先進行DFS的話，就可以保證每一次調用DFS訪問的頂點都處于同一個強連通分量下。

要確切地證明Kosaraju算法的正確性，需要證明這個命題：按照反向圖的逆后序順序在原圖中進行DFS，每一次DFS中所訪問的所有頂點都在同一個連通分量之中。上面說了這么多，只是定性解釋了為什么使用反向圖的逆后序這樣的序列可以達到目的，命題的后半句…在上面的分析中我們假設它是正確的，實際上這個命題需要嚴格的證明，下面就來證明在命題前半句的前提下，后半句的正確性。

要證明這個命題，有兩點需要證明(按照反向圖逆后序的順序進行DFS的前提下)：

• 每個和s強連通的頂點v必然會在調用dfs(G, s)中被訪問到;
• dfs(G, s)所達到的任意頂點v都必然是和s強連通的。

第一點，用反證法：假設存在一個頂點v不是在調用dfs(G,s)中被訪問到的，因為存在s -> v的路徑，說明v在調用dfs(G, s)之前就已經被訪問過了(否則和假設不符);又因為也存在v -> s的路徑，所以在調用dfs(G , v)后，s肯定也會被標記已訪問，這樣就調用不到dfs(G ,s)了，與我們假設會調用dfs(G, s)的前提矛盾了。所以原命題成立。

第二點，dfs(G, s)能達到頂點v，說明存在s -> v的路徑，要證明s和v是強連通的，只需再證明在原圖G中還存在一條v -> s的路徑，等價于在反向圖Gr中找到一條s -> v的路徑。由于是按照逆后序進行深度優先搜索，在Gr中dfs(Gr, v)一定是在dfs(Gr, s)之前返回的，否則逆后序就變成了[v, s]，原圖在dfs調用時就會先調用dfs(G, v)，此時如果原圖存在v -> s的路徑，那么dfs(G, v)被調用后，s會被標記已訪問，從而dfs(G, s)不會被調用到——這和我們假設的前提dfs(G, s)會被調用且達到v頂點矛盾。所以在Gr中dfs(Gr, v)一定會在dfs(Gr, s)之前返回，這有兩種情況

• dfs(Gr, v)在dfs(Gr, s)之前調用，并且也在dfs(Gr, s)的調用結束前結束。即dfs(Gr, v)調用 -> dfs(Gr, v)結束 -> dfs(Gr, s)調用 -> dfs(Gr, s)結束
• dfs(Gr, v)在dfs(Gr, s)之后調用，并且在dfs(Gr, s)的調用結束前結束。即dfs(Gr, s)調用 -> dfs(Gr, v)調用 -> dfs(Gr, v)結束 -> dfs(Gr, s)結束

第一種情況是不可能的。因為Gr中存在v -> s(G中有s -> v)，所以第一種情況中的調用不可能出現。第二種情況恰好說明了Gr中存在一條s -> v的路徑。得證!

如下，中間和右側的圖對應著上面兩種情況。

證明也證明了，代碼該給出了。

package Chap7; 
 
import java.util.LinkedList; 
 
/** 
 * 尋找有向圖中的強連通分量 
 */ 
public class KosarajuSCC { 
    // 用來標記已經訪問過的頂點，保證每個頂點值訪問一次 
    private boolean[] marked; 
    // 為每個連通分量標示一個id 
    private int[] id; 
    // 連通分量的個數 
    private int count; 
 
    public KosarajuSCC(DiGraph<?> graph) { 
        marked = new boolean[graph.vertexNum()]; 
        id = new int[graph.vertexNum()]; 
        // 對原圖G取反得到Gr 
        DFSorder order = new DFSorder(graph.reverse()); 
        // 按Gr的逆后序進行dfs 
        for (int s : order.reversePost()) { 
            if (!marked[s]) { 
                dfs(graph, s); 
                // 一次dfs調用就是一個連通分量，第一個連通分量id為0。 
                // 之后分配的id要自增，第二個連通分量的id為1，以此類推 
                count++; 
            } 
        } 
    } 
 
    private void dfs(DiGraph<?> graph, int v) { 
        // 將剛訪問到的頂點設置標志 
        marked[v] = true; 
        id[v] = count; 
        // 從v的所有鄰接點中選擇一個沒有被訪問過的頂點 
        for (int w : graph.adj(v)) { 
            if (!marked[w]) { 
                dfs(graph, w); 
            } 
        } 
    } 
 
    public boolean stronglyConnected(int v, int w) { 
        return id[v] == id[w]; 
    } 
 
    public int id(int v) { 
        return id[v]; 
    } 
 
    public int count() { 
        return count; 
    } 
 
    public static void main(String[] args) { 
        // 邊 
        int[][] edges = {{0, 1}, {0, 5}, {2, 3},{2, 0}, {3, 2}, 
                {3, 5}, {4, 2}, {4, 3},{4, 5}, {5, 4}, {6, 0}, {6, 4}, 
                {6, 9}, {7, 6}, {7, 8}, {8, 9},{8, 7}, {9, 10}, 
                {9, 11}, {10, 12}, {11, 4}, {11, 12}, {12, 9}}; 
 
        DiGraph<?> graph = new DiGraph<>(13, edges); 
        KosarajuSCC cc = new KosarajuSCC(graph); 
        // M是連通分量的個數 
        int M = cc.count(); 
        System.out.println(M + "個連通分量"); 
        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M]; 
        for (int i = 0; i < M; i++) { 
            components[i] = new LinkedList<>(); 
        } 
        // 將同一個id的頂點歸屬到同一個鏈表中 
        for (int v = 0; v < graph.vertexNum(); v++) { 
            components[cc.id(v)].add(v); 
        } 
        // 打印每個連通分量中的頂點 
        for (int i = 0; i < M; i++) { 
            for (int v : components[i]) { 
                System.out.print(v + " "); 
            } 
            System.out.println(); 
        } 
    } 
} 

針對一幅具體的有向圖，我們來看看Kosaraju算法的軌跡。左側的圖是對反向圖作DFS，得到逆后序排列是一個偽拓補序列;在右側的圖中，原有向圖按照這個序列進行DFS，總共對5個頂點進行了DFS，每次DFS都表示一個強連通分量(方框框起來的頂點集合)。

[圖片上傳失敗…(image-f58914-1510374691562)]

上面代碼中的測試樣例其實就是上面這個圖。它會打印如下信息

5個連通分量 
1  
0 2 3 4 5  
9 10 11 12  
6  
7 8  

對比上圖方框圈起來的內容，的確實是5個強連通分量。

順便一提，如果將圖中的強連通分量縮小成一個頂點，就能得到下圖。因為強連通分量和強連通分量之間不會形成環，所以逆后序得到的是真正的拓補序列。回到原有向圖中，按照該拓補序列順序DFS(順序是1, 0, 11, 6, 7)，可以發現算法總是優先選擇出度為0的頂點，進行DFS后刪除該頂點，再從剩余的圖中選擇出度為0的頂點繼續DFS。

對該算法的分析我都覺得蛋疼…嫌麻煩的直接記住結論即可。