摘要：只好特地拎出來記錄證明一下算法步驟第一步在逆圖上運行，將頂點按照逆后序方式壓入棧中顯然，這個過程作用在有向無環圖上得到的就是一個拓撲排序作用在非上得到的是一個偽拓撲排序第二步在原圖上按第一步的編號順序進行。等價于已知在逆圖中存在有向路徑。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 4 Section 2 有向圖

修改了方法void addEdge(v, w) 添加的邊為單向的， 從v到w

修改了方法adj(v) 返回的是從v指出去的邊連接的頂點

增加了方法Digraph reverse() 創建了一個反向邊的圖副本，因為有時候我們需要的是指向特定頂點的其他頂點

public class Digraph {
    private final int V;
    private int E;
    private Bag[] adj;

    public Digraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag[]) new Bag[V];
        for (int v = 0; v < V; v++)
            adj[v] = new Bag();
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }

    public Iterable adj(int v) {
        return adj[v];
    }

    public Digraph reverse() {
        Digraph R = new Digraph(V);
        for (int v = 0; v < V; v++)
            for (int w : adj(v))
                R.addEdge(w, v);
        return R;
    }
}

增加了構造函數DirectedDFS(G,sources) 一個source生成一棵樹，n個sources生成好n棵樹；也有可能是一棵樹，只是先找到了孫子，沒法通過孫子找爸爸和爺爺，后來輸入了爺爺，找到了爸爸，連到了孫子，形成了一棵大樹。

基本和有向圖沒區別

public class DirectedDFS {
    private boolean[] marked;

    public DirectedDFS(Digraph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    public DirectedDFS(Digraph G, Iterable sources) {
        marked = new boolean[G.V()];
        for (int s : sources)
            if (!marked[s]) dfs(G, s);
    }

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

    public boolean marked(int v) {
        return marked[v];
    }
}

標記-清除的垃圾箱

尋路

調度問題

拓撲排序 給定一副有向圖，將所有頂點排序，使得所有的有向邊從排在前面的元素指向后面的元素

有向無環圖 Directed Acyclic Graph （DAG）

方法boolean hasCycle() 有向環檢測

public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private Stack cycle; // vertices on a cycle (if one exists)
    private boolean[] onStack; // vertices on recursive call stack

    public DirectedCycle(Digraph G) {
        onStack = new boolean[G.V()];
        edgeTo = new int[G.V()];
        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) {
        onStack[v] = true; //這個變量是神來之筆。因為有好幾棵樹，但我只要查我所在的這棵樹。所以在遞歸的時候一路把這棵樹標成true，在返回之前再標回false。為下一棵樹可以循環再利用做準備。
        marked[v] = true;
        for (int w : G.adj(v))
            if (this.hasCycle()) return;
            else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            } else if (onStack[w]) { // 我遇到了組織，我們形成了一個環！
                cycle = new Stack();
                for (int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);//v壓了兩次，第一次作為箭頭終點，第二次作為箭頭起點
            }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable cycle() {
        return cycle;
    }
}

前提

當且僅當一幅圖是有向無環圖時，才能進行拓撲排序

一種拓撲排序的實現方式

深度優先搜索DFS

頂點排列順序

前序 遞歸調用之前將頂點加入隊列

后續 遞歸調用之后將頂點加入隊列

逆后續 遞歸調用之后將頂點壓入棧

頂點排列順序

就是記錄頂點的位置和方式不一樣

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;
    }
}

復雜度：

時間： V+E

（為什么我覺得Topological這個類沒干什么實事，DirectedCycle檢測是否是有向無環圖，DepthFirstOrder進行了排序。。。Topological感覺就封裝了一下）

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是相互可達的，則稱它們為強連通的(Strongly Connected)
（v到w有一條路徑，則w是從v可達的）

如果有向圖G的每兩個頂點都強連通，稱G是一個強連通圖。

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

兩個頂點是強連通的，當且僅當它們在同一個有向環中

性質

自反性

對稱性

傳遞性

Strongly Connected Components

算法步驟很簡單，但是原理很玄幻。。。只好特地拎出來記錄+證明一下

第一步：在逆圖G^R上運行DFS，將頂點按照逆后序（reversePost）方式壓入棧Stack s中
（顯然，這個過程作用在有向無環圖DAG上得到的就是一個拓撲排序；作用在非DAG上得到的是一個偽拓撲排序）

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

算法基于CC(ConnectedComponents)

CC按順序0~G.V()

SCC按順序s.pop()

SCC順序怎么得到？

類DepthFirstOrder

兩次DFS

圖示兩次DFS

復雜度：所需時間與空間與V+E成正比，連通性查詢為常數時間

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

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

連通性查詢： 數組id[]查詢，常數時間

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() { //復制書上的，感覺返回的不是強連通的個數N，因為從零開始計數，所以返回的是N-1
        return count;
    }
}

原圖

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

由于排版問題只畫了部分的有向邊

可見是否是環，應該從１開始排除，因為１是圖中最深的結點，最有可能只有指向１的，而沒有從１指出去的。通過開始一個一個排查，應該是一種比較好的想法。

證明的目標，就是最后一步 --- 每一顆搜索樹代表的就是一個強連通分量

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

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

而之所以DFS(s)能夠在DFS(v)之前被調用，是因為在對G獲取ReversePost-Order序列時，s出現在v之前，這也就意味著，v是在s之前加入該序列的(因為該序列使用棧作為數據結構，先加入的反而會在序列的后面)。

因此根據DFS調用的遞歸性質，DFS(v)應該在DFS(s)之前返回，而有當時在逆圖G^R中兩種情形滿足該條件：
DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END

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

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

頂點對的四種情況

w?v 強連通
w→v
w←v
w?v

問題：如何寫一個算法判斷從w到v是可達的嗎？
有向圖的可達性問題 和 連通性 有很大區別。 因為連通性是雙向的，可達性是單向的。

目前的解決辦法：傳遞閉包（其實就是一個類似于鄰接矩陣的矩陣，用來記錄是否連通）

給每個頂點創立了一棵樹，在每棵樹里有數組marked[V]，標記是否連通。

復雜度

空間：V*V

時間：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);
    }
}