無向圖

• 圖的表示方法：鄰接表
• dfs和bfs的區(qū)別：dfs是用棧，bfs用隊列

//連通圖
public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0; s < G.V(); s++) {
            dfs(G, s);
            count++;
        }
    }

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

    }
}

有向圖

• 有向無環(huán)圖(DAG): 不含有向環(huán)的有向圖

• 當且僅當一副有向圖是無環(huán)圖時它才能進行拓撲排序

• 有向圖中基于dfs的頂點排序：前序、后續(xù)、逆后續(xù)
  前序和后續(xù)用隊列，逆后續(xù)用棧

• 一副有向無環(huán)圖的拓撲排序就是所有頂點的逆后續(xù)排列（要先判斷有沒有環(huán)）

• 強連通 ：兩個頂點互聯(lián)可達，則這兩個頂點是強連通。若一個圖任意兩頂點都是強連通，則這幅有向圖也是強連通的。

• 計算強連通分量的Kosaraju算法：先使用dfs查找G的反向圖，得到所有頂點的逆后續(xù)，再用dfs處理，即可得到強連通分量

//強連通分量
public class KosarajuSCC {
    private boolean[] marked;
    private int[] id;
    private int count;

    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()) {
            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);
    }
}