image.png

拓?fù)渑判? 給定一個(gè)有向圖,將所有的頂點(diǎn)排序,使得所有的邊都是從排在前面的邊指向排在后面的邊.例如下面下邊示意圖:

image.png

拓?fù)渑判虻牡湫蛻?yīng)用:

4.2.4.2 有向圖中的環(huán)

在某些特定的有向圖依賴(lài)關(guān)系中是不允許出現(xiàn)環(huán)結(jié)構(gòu)的.例如java 類(lèi)依賴(lài)關(guān)系.
有向環(huán)檢測(cè): 如果有環(huán),在所有頂點(diǎn)中按照順序?qū)ふ?返回自己的頂點(diǎn).即找到了一個(gè)有向環(huán).
一幅有向圖的環(huán)的個(gè)數(shù)有可能是圖大小的指數(shù)級(jí)別,所以一般情況下只需要找到一個(gè)有向環(huán)即可判斷,而不需要找出所有的環(huán).因此有向無(wú)環(huán)圖就表現(xiàn)的尤為突出.

定義：

有向無(wú)環(huán)圖[DAG （Directed acyclic graph）]就是一副不含環(huán)的有向圖.

檢測(cè)是否是有向無(wú)環(huán)圖.采用深度優(yōu)先搜索.維護(hù)一個(gè)遞歸調(diào)用棧來(lái)記錄當(dāng)前在遍歷的有向路徑,一旦我們找到了一條邊v→ w ,并且w已經(jīng)存在當(dāng)前遞歸棧中,則表示找到了一個(gè)有向環(huán),同時(shí)如果找不到這樣一條邊,則說(shuō)明圖是有向無(wú)環(huán)圖.

package algorithm.algorithmbook.graph;
import java.util.Stack;
/**
 * description:尋找有向環(huán)
 *
 * @author leon
 * @date 18-2-26.
 */
public class DirectCycle {
    private int[] edgeTo;
    private boolean[] marked;
    //用于存放環(huán)的所有頂點(diǎn),如果存在環(huán)
    private Stack<Integer> cycles;
    //遞歸調(diào)用的棧上的所有頂點(diǎn)
    private boolean[] onStack;
    public DirectCycle(Digraph digraph) {
        onStack = new boolean[digraph.V()];
        marked = new boolean[digraph.V()];
        edgeTo = new int[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]) {
                dfs(digraph, v);
            }
        }
    }
    private void dfs(Digraph digraph, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : digraph.adj(v)) {
            //特別的處理環(huán)的,如果已經(jīng)找到了環(huán)則跳出循環(huán)
            if (this.hashCycle()) {
                return;
            }
            //進(jìn)行深度優(yōu)先遍歷
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(digraph, w);
            }
            //如果已經(jīng)marked了,說(shuō)明已經(jīng)查找過(guò)頂點(diǎn),也就是出現(xiàn)了環(huán)
            else if (onStack[w]) {
                cycles = new Stack<>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycles.push(x);
                }
                cycles.push(w);
                cycles.push(v);
            }
            onStack[v] = false;
        }
    }
    public boolean hashCycle() {
        return !cycles.empty();
    }
    public Iterable<Integer> cycle() {
        return cycles;
    }
}

4.2.3.4 頂點(diǎn)的深度優(yōu)先次序和拓?fù)渑判?/h6>

命題E:

只有有向無(wú)環(huán)圖才能進(jìn)行拓?fù)渑判?

實(shí)際上我們已經(jīng)見(jiàn)過(guò)一種拓?fù)渑判虻乃惴?只需要添加一行代碼就可以由標(biāo)準(zhǔn)的深度優(yōu)先搜索完成這項(xiàng)任務(wù)!引入一種搜索排序,”有向圖中基于深度優(yōu)先的頂點(diǎn)搜索排序”.他的思想是深度優(yōu)先搜索只會(huì)訪問(wèn)所有的頂點(diǎn)一次.遍歷這個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)際上能訪問(wèn)圖中的所有頂點(diǎn),而遍歷的順序取決與這個(gè)數(shù)據(jù)結(jié)構(gòu)是遞歸前還是之后進(jìn)行保存.一般情況人們關(guān)注3中情況:

1.前序遍歷 (pre) :在遞歸前將頂點(diǎn)加入隊(duì)列

2.后續(xù)遍歷(post):在遞歸后將頂點(diǎn)加入隊(duì)列

3.逆后續(xù)(reversePost): 把后續(xù)遍歷的順序反轉(zhuǎn)采用棧保存,剛好可以反過(guò)來(lái)).在遞歸后將頂點(diǎn)加入棧.

image.png

執(zhí)行深度優(yōu)先搜索的 3中排序過(guò)程:

image.png

package algorithm.algorithmbook.graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
/**
 * description:有向圖深度優(yōu)先排序的幾種方式
 * <p>
 * 這里根據(jù)在遞歸前,后 進(jìn)行頂點(diǎn)保存的順序分成前序,后序,逆后序
 * 1.前序遍歷 (pre) :在遞歸前將頂點(diǎn)加入隊(duì)列
 * 2.后續(xù)遍歷(post):在遞歸后將頂點(diǎn)加入隊(duì)列
 * 3.逆后續(xù)(reversePost): 把后續(xù)遍歷的順序反轉(zhuǎn)采用棧保存,剛好可以反過(guò)來(lái)).在遞歸后將頂點(diǎn)加入棧.
 *
 * @author leon
 * @date 18-2-27.
 */
public class DirectDeepFirstOrder {
    private boolean[] marked;
    private Queue<Integer> preQ;
    private Queue<Integer> postQ;
    private Stack<Integer> reversePost;
    public DirectDeepFirstOrder(Digraph g) {
        marked = new boolean[g.V()];
        preQ = new ArrayDeque<>();
        postQ = new ArrayDeque<>();
        reversePost = new Stack<>();
        for (int v = 0; v < g.V(); v++) {
            if (!marked[v]) {
                dfs(g, v);
            }
        }
    }
    /**
     * 深度優(yōu)先遍歷遞歸
     *
     * @param g 圖
     * @param v 需要遞歸的頂點(diǎn)
     */
    private void dfs(Digraph g, int v) {
        preQ.offer(v);
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        postQ.offer(v);
        reversePost.push(v);
    }
    /**
     * 前序
     *
     * @return 排序列表
     */
    public Iterable<Integer> pre() {
        return preQ;
    }
    /**
     * 后序
     *
     * @return 排序列表
     */
    public Iterable<Integer> post() {
        return postQ;
    }
    /**
     * 逆后序
     *
     * @return 排序列表
     */
    public Iterable<Integer> reversePost() {
        return reversePost;
    }
}

命題:

一副有向無(wú)環(huán)圖的的拓?fù)渑判蚣此许旤c(diǎn)的逆后序排序

證明:

對(duì)于任意邊v→ w,在調(diào)用dfs(v)時(shí)以下三種情況之一會(huì)滿足:
1.dfs(w)已經(jīng)調(diào)用過(guò)并且已經(jīng)返回了(w已經(jīng)被標(biāo)記了)
2.dfs(w)還沒(méi)有調(diào)用,此時(shí)會(huì)繼續(xù)接下來(lái)調(diào)用dfs(w),并且在 dfs(v)之前調(diào)用,并且標(biāo)記.
3.dfs(w)已經(jīng)調(diào)用并且沒(méi)有返回.證明的關(guān)鍵在于,需要證明這種情況在有向無(wú)環(huán)圖中是不可能出現(xiàn)的,則可以確定v→ w 的dfs(x) 是有順序的.因?yàn)?如果 dfs(w)已經(jīng)調(diào)用,但是沒(méi)有返回,則說(shuō)明有邊w→ v存在,然而本身有v→ w ,這樣就形成了一個(gè)環(huán).與有向無(wú)環(huán)圖有矛盾,故情況3是不存在的.
綜上所述:任意一條邊的dfs(w) 都會(huì)在dfs(v)之前標(biāo)記,也就是說(shuō) 在排名靠后w的dfs(w) 比排名靠前v的dfs(v)先標(biāo)記,把標(biāo)記列表倒序就得到排名靠前的v→ w的頂點(diǎn).

package algorithm.algorithmbook.graph;
/**
 * description:拓?fù)渑判? *
 * @author leon
 * @date 18-2-26.
 */
public class Topological {
    private Iterable<Integer> orderList;
    public Topological(Digraph digraph) {
        DirectCycle directCycle = new DirectCycle(digraph);
        if (!directCycle.hashCycle()) {
            DirectDeepFirstOrder directDeepFirstOrder = new DirectDeepFirstOrder(digraph);
            orderList = directDeepFirstOrder.reversePost();
        }
    }
    /**
     * 是否是有向無(wú)環(huán)圖
     *
     * @return
     */
    public boolean isDAG() {
        return orderList != null;
    }
    /**
     * 拓?fù)渑判?     *
     * @return
     */
    Iterable<Integer> order() {
        return orderList;
    }
    /**
     * test
     *
     * @param args
     */
    public static void main(String[] args) {
        String fileName = args[0];
        String sepatetor = args[1];
        SymbolDirectGraph symbolGraph = new SymbolDirectGraph(fileName, sepatetor);
        Topological topological = new Topological(symbolGraph.graph());
        if (!topological.isDAG()) {
            return;
        }
        for (int v : topological.orderList) {
            //通過(guò)索引表來(lái)獲取圖中對(duì)應(yīng)的 名字
            System.out.println(symbolGraph.name(v));
        }
    }
}

命題G:

使用深度優(yōu)先搜索對(duì)無(wú)向圖進(jìn)行拓?fù)渑判虻乃钑r(shí)間與V+E成正比.

證明:

由代碼可知,拓?fù)渑判蛐枰M(jìn)行兩次,1.進(jìn)行是否有環(huán)判斷,2 進(jìn)行逆后序排序. 每次操作都訪問(wèn)了頂點(diǎn)和邊,即是V+E 的倍數(shù)關(guān)系.

4.2.5 有向圖中的強(qiáng)連通性

定義:

如果有向圖中 w和v 雙向可到達(dá)即存在v到w的有向路徑,也存在w到v的有向路徑,稱(chēng)為強(qiáng)連通.如果一副有向圖總?cè)我鈨牲c(diǎn)之間都是強(qiáng)連通,則稱(chēng)這幅有向圖也是強(qiáng)連通的.

兩個(gè)頂點(diǎn)是強(qiáng)連通.當(dāng)且僅當(dāng)他們都是同在一個(gè)有向環(huán)中.

強(qiáng)連通分量特點(diǎn):

• 自反性:任意頂點(diǎn)v 和自己都是強(qiáng)連通的.
• 對(duì)稱(chēng)性: v和w 是強(qiáng)連通,那么w和v也是強(qiáng)連通
• 傳遞性: v和w 是強(qiáng)連通,w和x 是強(qiáng)連通.那么v 和x 是強(qiáng)連通.

強(qiáng)連通性將所有頂點(diǎn)分成一些平等的部分,每個(gè)部分是由所組成強(qiáng)連通的頂點(diǎn)最大子集組成.把這些最大子集稱(chēng)為強(qiáng)連通分量.包含V個(gè)頂點(diǎn)的有向圖包含 1-V個(gè)強(qiáng)連通分量;一個(gè)強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量(也就是整個(gè)圖);而一個(gè)無(wú)環(huán)圖則包含V個(gè)強(qiáng)連通分量(每個(gè)頂點(diǎn)都是自己的強(qiáng)連通分量,所以強(qiáng)連通分量就是每個(gè)頂點(diǎn)).因?yàn)閺?qiáng)連通是針對(duì)頂點(diǎn)而不是邊,所以會(huì)出現(xiàn)有些邊連接的兩個(gè)頂點(diǎn)出現(xiàn)在同一個(gè)強(qiáng)連通分量中,而有些邊連接的兩個(gè)頂點(diǎn)則出現(xiàn)在不同的強(qiáng)連通分量中.

image.png

4.2.5.2 應(yīng)用舉例

在理解有向圖的結(jié)構(gòu)時(shí),強(qiáng)連通性是一個(gè)重要的特點(diǎn).他突出了相互關(guān)聯(lián)的幾組頂點(diǎn)(強(qiáng)連通分量).例如強(qiáng)連通分量能夠幫組教科書(shū)的作者決定那些話題應(yīng)該歸為一類(lèi),幫助程序員組織程序的模塊;表示哪些食物鏈中的物種應(yīng)該在一個(gè)生態(tài)圈中.
強(qiáng)連通分量API

kosaraju算法:

1.在給定有向圖G,使用DeepFirstOrder計(jì)算他的反向圖G^R的逆后序排序.

2.在G圖中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索,但是需要按照剛才計(jì)算出的順序訪問(wèn)所有未標(biāo)記過(guò)的頂點(diǎn)(而非標(biāo)準(zhǔn)的順序訪問(wèn)).

3.在構(gòu)造函數(shù)中,所有同一個(gè)遞歸dfs()調(diào)用中訪問(wèn)到的頂點(diǎn)都在同一個(gè)強(qiáng)連通分量中,將他們按照CC的方式識(shí)別出來(lái).

強(qiáng)連通性: 回答”給定的兩點(diǎn)是強(qiáng)連通的嗎? 這幅圖中含有多少個(gè)強(qiáng)連通分量 ?”

因?yàn)?Kosaraju 方法借助了有向圖求反向圖,然后再計(jì)算 逆序排序.

能不能用和 無(wú)向圖相同的效率解決有向圖圖的強(qiáng)連通問(wèn)題.Tarjan提出了一個(gè)解決方案.而且這個(gè)簡(jiǎn)單的解決方案令人驚訝.