數(shù)據(jù)結(jié)構(gòu)與算法–圖論之尋找連通分量、強(qiáng)連通分量

作者：sunhaiyu

找無(wú)向圖的連通分量

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

下面這幅圖，有3個(gè)連通分量。

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

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

package Chap7;import java.util.LinkedList;public class CC {    // 用來(lái)標(biāo)記已經(jīng)訪問(wèn)過(guò)的頂點(diǎn)，保證每個(gè)頂點(diǎn)值訪問(wèn)一次    private boolean[] marked;    // 為每個(gè)連通分量標(biāo)示一個(gè)id    private int[] id;    // 連通分量的個(gè)數(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)用就是一個(gè)連通分量，第一個(gè)連通分量id為0。                // 之后分配的id要自增，第二個(gè)連通分量的id為1，以此類推                count++;            }        }    }    private void dfs(UndiGraph<?> graph, int v) {        // 將剛訪問(wèn)到的頂點(diǎn)設(shè)置標(biāo)志        marked[v] = true;        id[v] = count;        // 從v的所有鄰接點(diǎn)中選擇一個(gè)沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)        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是連通分量的個(gè)數(shù)        int M = cc.count();        System.out.println(M + "個(gè)連通分量");        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M];        for (int i = 0; i < M; i++) {            components[i] = new LinkedList<>();        }        // 將同一個(gè)id的頂點(diǎn)歸屬到同一個(gè)鏈表中        for (int v = 0; v < graph.vertexNum(); v++) {            components[cc.id(v)].add(v);        }        // 打印每個(gè)連通分量中的頂點(diǎn)        for (int i = 0; i < M; i++) {            for (int v : components[i]) {                System.out.print(v+ " ");            }            System.out.println();        }    }}

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

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

對(duì)比上圖，吻合！

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

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

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

尋找有向圖的強(qiáng)連通分量

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

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

下圖中就含有5個(gè)強(qiáng)連通分量。

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

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

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

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

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

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

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

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

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

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

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

要證明這個(gè)命題，有兩點(diǎn)需要證明（按照反向圖逆后序的順序進(jìn)行DFS的前提下）：

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

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

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

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

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

package Chap7;import java.util.LinkedList;/** * 尋找有向圖中的強(qiáng)連通分量 */public class KosarajuSCC {    // 用來(lái)標(biāo)記已經(jīng)訪問(wèn)過(guò)的頂點(diǎn)，保證每個(gè)頂點(diǎn)值訪問(wèn)一次    private boolean[] marked;    // 為每個(gè)連通分量標(biāo)示一個(gè)id    private int[] id;    // 連通分量的個(gè)數(shù)    private int count;    public KosarajuSCC(DiGraph<?> graph) {        marked = new boolean[graph.vertexNum()];        id = new int[graph.vertexNum()];        // 對(duì)原圖G取反得到Gr        DFSorder order = new DFSorder(graph.reverse());        // 按Gr的逆后序進(jìn)行dfs        for (int s : order.reversePost()) {            if (!marked[s]) {                dfs(graph, s);                // 一次dfs調(diào)用就是一個(gè)連通分量，第一個(gè)連通分量id為0。                // 之后分配的id要自增，第二個(gè)連通分量的id為1，以此類推                count++;            }        }    }    private void dfs(DiGraph<?> graph, int v) {        // 將剛訪問(wèn)到的頂點(diǎn)設(shè)置標(biāo)志        marked[v] = true;        id[v] = count;        // 從v的所有鄰接點(diǎn)中選擇一個(gè)沒(méi)有被訪問(wèn)過(guò)的頂點(diǎn)        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是連通分量的個(gè)數(shù)        int M = cc.count();        System.out.println(M + "個(gè)連通分量");        LinkedList<Integer>[] components = (LinkedList<Integer>[]) new LinkedList[M];        for (int i = 0; i < M; i++) {            components[i] = new LinkedList<>();        }        // 將同一個(gè)id的頂點(diǎn)歸屬到同一個(gè)鏈表中        for (int v = 0; v < graph.vertexNum(); v++) {            components[cc.id(v)].add(v);        }        // 打印每個(gè)連通分量中的頂點(diǎn)        for (int i = 0; i < M; i++) {            for (int v : components[i]) {                System.out.print(v + " ");            }            System.out.println();        }    }}

針對(duì)一幅具體的有向圖，我們來(lái)看看Kosaraju算法的軌跡。左側(cè)的圖是對(duì)反向圖作DFS，得到逆后序排列是一個(gè)偽拓補(bǔ)序列；在右側(cè)的圖中，原有向圖按照這個(gè)序列進(jìn)行DFS，總共對(duì)5個(gè)頂點(diǎn)進(jìn)行了DFS，每次DFS都表示一個(gè)強(qiáng)連通分量（方框框起來(lái)的頂點(diǎn)集合）。

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

上面代碼中的測(cè)試樣例其實(shí)就是上面這個(gè)圖。它會(huì)打印如下信息

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

對(duì)比上圖方框圈起來(lái)的內(nèi)容，的確實(shí)是5個(gè)強(qiáng)連通分量。

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

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

生成海報(bào)

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