一種拓?fù)渑判虻膶?shí)現(xiàn)方式

深度優(yōu)先搜索DFS

頂點(diǎn)排列順序

前序 遞歸調(diào)用之前將頂點(diǎn)加入隊(duì)列

后續(xù) 遞歸調(diào)用之后將頂點(diǎn)加入隊(duì)列

逆后續(xù) 遞歸調(diào)用之后將頂點(diǎn)壓入棧

頂點(diǎn)排列順序

就是記錄頂點(diǎn)的位置和方式不一樣

public class DepthFirstOrder {
    private boolean[] marked;
    private Queue pre; // vertices in preorder
    private Queue post; // vertices in postorder
    private Stack reversePost; // vertices in reverse postorder

    public DepthFirstOrder(Digraph G) {
        pre = new Queue();
        post = new Queue();
        reversePost = new Stack();
        marked = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v]) dfs(G, v);
    }

    private void dfs(Digraph G, int v) {
        pre.enqueue(v);
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
        post.enqueue(v);
        reversePost.push(v);
    }

    public Iterable pre() {
        return pre;
    }

    public Iterable post() {
        return post;
    }

    public Iterable reversePost() {
        return reversePost;
    }
}

復(fù)雜度：

時(shí)間： V+E

（為什么我覺(jué)得Topological這個(gè)類(lèi)沒(méi)干什么實(shí)事，DirectedCycle檢測(cè)是否是有向無(wú)環(huán)圖，DepthFirstOrder進(jìn)行了排序。。。Topological感覺(jué)就封裝了一下）

public class Topological {
    private Iterable order; // topological order

    public Topological(Digraph G) {
        DirectedCycle cyclefinder = new DirectedCycle(G);
        if (!cyclefinder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost(); //排序方式
        }
    }

    public Iterable order() {
        return order;
    }

    public boolean isDAG() {
        return order == null;
    }
}

定義

w和v是相互可達(dá)的，則稱(chēng)它們?yōu)閺?qiáng)連通的(Strongly Connected)
（v到w有一條路徑，則w是從v可達(dá)的）

如果有向圖G的每?jī)蓚€(gè)頂點(diǎn)都強(qiáng)連通，稱(chēng)G是一個(gè)強(qiáng)連通圖。

有向圖的極大強(qiáng)連通子圖，稱(chēng)為強(qiáng)連通分量(Strongly Connected Components/Strong Components)

兩個(gè)頂點(diǎn)是強(qiáng)連通的，當(dāng)且僅當(dāng)它們?cè)谕粋€(gè)有向環(huán)中

性質(zhì)

自反性

對(duì)稱(chēng)性

傳遞性

Strongly Connected Components

算法步驟很簡(jiǎn)單，但是原理很玄幻。。。只好特地拎出來(lái)記錄+證明一下

第一步：在逆圖G^R上運(yùn)行DFS，將頂點(diǎn)按照逆后序（reversePost）方式壓入棧Stack s中
（顯然，這個(gè)過(guò)程作用在有向無(wú)環(huán)圖DAG上得到的就是一個(gè)拓?fù)渑判?；作用在非DAG上得到的是一個(gè)偽拓?fù)渑判颍?/p>

第二步：在原圖G上按第一步s.pop()的編號(hào)順序進(jìn)行DFS。
（棧的特點(diǎn)是FILO，先進(jìn)后出）

算法基于CC(ConnectedComponents)

CC按順序0~G.V()

SCC按順序s.pop()

SCC順序怎么得到？

類(lèi)DepthFirstOrder

兩次DFS

圖示兩次DFS

復(fù)雜度：所需時(shí)間與空間與V+E成正比，連通性查詢(xún)?yōu)槌?shù)時(shí)間

時(shí)間： 處理有向圖的反向圖，+ 2次DFS 這三步所需的時(shí)間都與V+E成正比

空間： 反向復(fù)制一副有向圖的空間與V+E成正比

連通性查詢(xún)： 數(shù)組id[]查詢(xún)，常數(shù)時(shí)間

public class KosarajuSCC {
    private boolean[] marked; // reached vertices
    private int[] id; // component identifiers
    private int count; // number of strong components

    public KosarajuSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder order = new DepthFirstOrder(G.reverse());
        for (int s : order.reversePost())
            if (!marked[s]) {
                dfs(G, s);
                count++;
            }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w]) dfs(G, w);
    }

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

    public int id(int v) {
        return id[v];
    }

    public int count() { //復(fù)制書(shū)上的，感覺(jué)返回的不是強(qiáng)連通的個(gè)數(shù)N，因?yàn)閺牧汩_(kāi)始計(jì)數(shù)，所以返回的是N-1
        return count;
    }
}

原圖

pop順序　　　→→→→　　　　　→→→→→→→→→
7 → 8　6 → 9 → 11　10 → 12　0 → 5 → 4 → 3 → 2　1
　←　　　　　←←←←←←　　　←←←←←←←　　　　　　

由于排版問(wèn)題只畫(huà)了部分的有向邊

可見(jiàn)是否是環(huán)，應(yīng)該從１開(kāi)始排除，因?yàn)椋笔菆D中最深的結(jié)點(diǎn)，最有可能只有指向１的，而沒(méi)有從１指出去的。通過(guò)開(kāi)始一個(gè)一個(gè)排查，應(yīng)該是一種比較好的想法。

證明的目標(biāo)，就是最后一步 --- 每一顆搜索樹(shù)代表的就是一個(gè)強(qiáng)連通分量

首先 最后一步是在原圖G中通過(guò)s找到其他頂點(diǎn)v的，即從s→v是可達(dá)的。
那么我們需要證明，原圖G中v→s也是可達(dá)的。

等價(jià)于已知：在逆圖G^R中存在有向路徑v→s。
那么要證明：逆圖G^R中從s→v是可達(dá)的。

而之所以DFS(s)能夠在DFS(v)之前被調(diào)用，是因?yàn)樵趯?duì)G獲取ReversePost-Order序列時(shí)，s出現(xiàn)在v之前，這也就意味著，v是在s之前加入該序列的(因?yàn)樵撔蛄惺褂脳Ｗ鳛閿?shù)據(jù)結(jié)構(gòu)，先加入的反而會(huì)在序列的后面)。

因此根據(jù)DFS調(diào)用的遞歸性質(zhì)，DFS(v)應(yīng)該在DFS(s)之前返回，而有當(dāng)時(shí)在逆圖G^R中兩種情形滿(mǎn)足該條件：
DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END

第一種情形下，調(diào)用DFS(v)卻沒(méi)能在它返回前遞歸調(diào)用DFS(s)，與在逆圖G^R中存在有向路徑v→s相矛盾的，因此不可取。
故情形二為唯一符合邏輯的調(diào)用過(guò)程。而根據(jù)DFS(s) START -> DFS(v) START可以推導(dǎo)出在逆圖G^R中存在有向路徑s→v。

所以從s到v以及v到s都有路徑可達(dá)，證明完畢。

頂點(diǎn)對(duì)的四種情況

w?v 強(qiáng)連通
w→v
w←v
w?v

問(wèn)題：如何寫(xiě)一個(gè)算法判斷從w到v是可達(dá)的嗎？
有向圖的可達(dá)性問(wèn)題 和 連通性 有很大區(qū)別。 因?yàn)檫B通性是雙向的，可達(dá)性是單向的。

目前的解決辦法：傳遞閉包（其實(shí)就是一個(gè)類(lèi)似于鄰接矩陣的矩陣，用來(lái)記錄是否連通）

給每個(gè)頂點(diǎn)創(chuàng)立了一棵樹(shù)，在每棵樹(shù)里有數(shù)組marked[V]，標(biāo)記是否連通。

復(fù)雜度

空間：V*V

時(shí)間：V*(V+E)

public class TransitiveClosure {
    private DirectedDFS[] all;

    TransitiveClosure(Digraph G) {
        all = new DirectedDFS[G.V()];
        for (int v = 0; v < G.V(); v++)
            all[v] = new DirectedDFS(G, v);
    }

    boolean reachable(int v, int w) {
        return all[v].marked(w);
    }
}