图

无向图

• 图的表示方法：邻接表
• dfs和bfs的区别：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);

    }
}

有向图

• 有向无环图(DAG): 不含有向环的有向图

• 当且仅当一副有向图是无环图时它才能进行拓扑排序

• 有向图中基于dfs的顶点排序：前序、后续、逆后续
  前序和后续用队列，逆后续用栈

• 一副有向无环图的拓扑排序就是所有顶点的逆后续排列（要先判断有没有环）

• 强连通 ：两个顶点互联可达，则这两个顶点是强连通。若一个图任意两顶点都是强连通，则这幅有向图也是强连通的。

• 计算强连通分量的Kosaraju算法：先使用dfs查找G的反向图，得到所有顶点的逆后续，再用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);
    }
}