無向圖

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

//連通圖
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)的有向圖

• 當(dāng)且僅當(dāng)一副有向圖是無環(huán)圖時(shí)它才能進(jìn)行拓?fù)渑判?/p>

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

• 一副有向無環(huán)圖的拓?fù)渑判蚓褪撬许旤c(diǎn)的逆后續(xù)排列（要先判斷有沒有環(huán)）

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

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

//強(qiáng)連通分量
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);
    }
}