作者：sunhaiyu

找無向圖的連通分量

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

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

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

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

package Chap7;import java.util.LinkedList;public class CC {    // 用來標(biāo)記已經(jīng)訪問過的頂點，保證每個頂點值訪問一次    private boolean[] marked;    // 為每個連通分量標(biāo)示一個id    private int[] id;    // 連通分量的個數(shù)    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調(diào)用就是一個連通分量，第一個連通分量id為0。                // 之后分配的id要自增，第二個連通分量的id為1，以此類推                count++;            }        }    }    private void dfs(UndiGraph<?> graph, int v) {        // 將剛訪問到的頂點設(shè)置標(biāo)志        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是連通分量的個數(shù)        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();        }    }}

程序?qū)⒋蛴∪缦滦畔?/p>

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

對比上圖，吻合！

深度優(yōu)先搜索的應(yīng)用——判斷無向圖是否有環(huán)

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

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]) {               // 剛開始沒有頂點被訪問過，所以當(dāng)前正訪問和上一個被訪問的頂點設(shè)置為起點s。當(dāng)dfs被遞歸調(diào)用一次后，當(dāng)前正訪問的參數(shù)v是s的一個鄰接點，而上一個被訪問的參數(shù)u是s，符合                dfs(graph, s, s);            }        }    }    // 修改過的DFS，v表示當(dāng)前正訪問的頂點，u表示上一個訪問的頂點    private void dfs(UndiGraph<?> graph, int v, int u) {        // 將剛訪問到的頂點設(shè)置標(biāo)志        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算法，新增了一個參數(shù)u，表示上一個被訪問的頂點。判斷是否有環(huán)，關(guān)鍵就是那句else if (w != u)。注意是w和u比較。為什么這樣就能判斷有環(huán)了呢？如果當(dāng)前訪問的頂點v的這個鄰接點w是之前已經(jīng)訪問過的，且不是上一個訪問的頂點，那么該無向圖就有環(huán)。也就是下圖這種情況。

w已經(jīng)被訪問過且w == u的情況，無環(huán)。也就是下圖的情況

尋找有向圖的強連通分量

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

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

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

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

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

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

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

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

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

現(xiàn)在可以說說Kosaraju算法的思路：

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

上圖是取反后的有向圖。設(shè)原圖為G，取反后的圖為Gr。深度優(yōu)先搜索Gr有兩種可能：

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

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

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

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

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

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

如下，中間和右側(cè)的圖對應(yīng)著上面兩種情況。

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

package Chap7;import java.util.LinkedList;/** * 尋找有向圖中的強連通分量 */public class KosarajuSCC {    // 用來標(biāo)記已經(jīng)訪問過的頂點，保證每個頂點值訪問一次    private boolean[] marked;    // 為每個連通分量標(biāo)示一個id    private int[] id;    // 連通分量的個數(shù)    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調(diào)用就是一個連通分量，第一個連通分量id為0。                // 之后分配的id要自增，第二個連通分量的id為1，以此類推                count++;            }        }    }    private void dfs(DiGraph<?> graph, int v) {        // 將剛訪問到的頂點設(shè)置標(biāo)志        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是連通分量的個數(shù)        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算法的軌跡。左側(cè)的圖是對反向圖作DFS，得到逆后序排列是一個偽拓補序列；在右側(cè)的圖中，原有向圖按照這個序列進行DFS，總共對5個頂點進行了DFS，每次DFS都表示一個強連通分量（方框框起來的頂點集合）。

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

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

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

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

順便一提，如果將圖中的強連通分量縮小成一個頂點，就能得到下圖。因為強連通分量和強連通分量之間不會形成環(huán)，所以逆后序得到的是真正的拓補序列?；氐皆邢驁D中，按照該拓補序列順序DFS（順序是1, 0, 11, 6, 7），可以發(fā)現(xiàn)算法總是優(yōu)先選擇出度為0的頂點，進行DFS后刪除該頂點，再從剩余的圖中選擇出度為0的頂點繼續(xù)DFS。

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

生成海報

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。