無向圖
- 圖的表示方法：鄰接表
- 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);
}
}
