一、注意事項
實作方法可分為遞歸和非遞歸。這裡主要想說明一些注意事項。1.在實作圖的深度優先周遊時搜尋節點的順序每次必須固定，回溯到某一點後會按照這個固定的順序繼續搜尋當時還未搜尋的節點，否則會因重複搜尋相同的節點造成死循環。另外，為了避免出現環的重複搜尋，需要記錄已經搜尋過的節點。2.在采用非遞歸方式實作深度優先周遊時，尤其值得注意的是需要記錄每個節點目前搜尋到的節點，下次回溯到此節點時，會從該處繼續搜尋，進而避免重複搜尋相同節點。
還有一點就是關于搜尋與周遊的差別，這在上一篇文章中也已經提到了。注意圖既可以是有向圖，又可以是無向圖。既可以是連通圖，也可以是非連通。既可以用鄰接表表示，又可以用鄰接矩陣表示。
用數組模拟棧實作圖的深度優先周遊可以參考之後的另一篇部落格《Ford-Fulkerson算法 java實作》中的dfs函數
二、理論
2.1.僞代碼
輸入圖既可以是有向圖也可以是無向圖.time是一個全局變量，用來計算時間戳。
DFS(G)
for each vertex u in G.v
u.color = WHITE
u.pi = NIL
time = 0
for each vertex u in G.V
if u.color == WHITE
DFS-VISIT(G,u)
DFS-VISIT(G,u)
time = time+1 // white vertext u has just been discovered
u.d = time // u.d是發現時間
u.color = GRAY
for each v in G:Adj[u] // explore edge (u,v)
if v.color == WHITE
v.pi = u
DFS-VISIT(G,v)
u.color = BLACK // blacken u; it is finished
time = time+1
u.f = time // u.f 是完成時間
聚合分析，時間複雜度 theta(V+E).
2.2. 性質
節點的發現時間和完成時間具有括号化結構。
括号化定理：在對有向或無向圖G=(V,E)進行的任意深度優先搜尋中，對于任意兩個節點u和v來說，下面的三種情況隻有一種成立：
1.區間[u.d,u.f]和區間[v.d,v.f]完全分離，在深度優先森林中，節點u不是節點v的後代，節點v也不是節點u的後代；
2.區間[u,d,u.f]完全包含在區間[v.d,v.f]中，在深度優先森林中，節點u是節點v的後代；
3.區間[v.d,v.f]完全包含在區間[u.f,u.d]中，在深度優先森林中，節點v是節點u的後代。
白色路徑定理：在有向圖或無向圖G = (V,E)的深度優先森林中，節點v是節點u的後代當且僅當在發現節點u的時間u.d，存在一條從節點u到節點v的全部由白色節點所構成的路徑。
在對無向圖G進行深度優先搜尋時，每條邊要麼是樹邊，要麼是後向邊。
樹邊：為深度優先森林G_pi中的邊。如果節點v是因算法對邊(u,v)的搜尋而首先被發現，則(u,v)是一條樹邊。
後向邊：後向邊(u,v)是将節點u連接配接到其在深度優先樹中（一個）祖先節點v的邊。由于有向圖可以有自循環，自循環也被認為是後向邊。
前向邊：是指将節點u連接配接到其在深度優先樹中一個後代節點v的邊(u,v)。
橫向邊：其他所有邊。
深度優先森林：深度優先搜尋的前驅子圖形成一個由多棵深度優先樹構成的深度優先森林。
關于深度優先森林這裡說明一下，在廣度優先搜尋中，前驅子圖形成一棵樹，但是在深度優先搜尋中，前驅子圖可能有多棵樹組成。通過上面的僞代碼可以看到，深度優先搜尋中可能會從多個點開始搜尋。
三、應用
圖的搜尋算法應用非常廣泛，這裡暫時隻舉2例，後面的文章中會有更多的執行個體。
1.拓撲排序
對于一個有向無環圖G=(V,E)來說，其拓撲排序是G中所有節點的一種線性關系，該次序滿足如下條件：如果圖G包含邊(u,v)，則節點u在拓撲排序中處于節點v的前面（如果圖G包含環路，則不可能排出一個線性次序）。
僞代碼：
TOPOLOGICAL-SORT（G）
call DFS(G) to compute finishing times v.f for each vertex
as each vertex is finished,insert it onto the front of a linked list
return the linked list of vertices
引理：一個有向圖 G = (V,E) 是無環的當且僅當對其進行的深度優先搜尋不産生後向邊。
我們下面的代碼邏輯與上面僞代碼中的并不相同，下面代碼是從出度為0的節點倒着搜的。這在圖采用鄰接矩陣的時候是可以的，但是采用鄰接表的話，每次都需要周遊整個圖才能找到所有指向自己的節點，比較複雜。另外，完全可以采用僞代碼中的方式，對每個節點調用DFS，這種方式無論鄰接表還是鄰接矩陣都可以。
import java.util.*;
public class Topology
{
static final int MAX = 20; //最大點數
static int[][] g; //圖
static LinkedList<Integer> queue; //儲存排序結果
static int[] ingoing; //記錄節點入度
static int[] outgoing;//記錄節點出度
static int[] used;
static int ver;
static int edge;
static void tplgOrd(){
//從所有出度為0的點開始周遊
for(int i=1;i<=ver;i++){
if(outgoing[i] == 0)
helper(i);
}
}
static void helper(int index){
//入度為0，說明沒有先驅節點了
if(ingoing[index]==0) {
if(used[index]==0){used[index] = 1;queue.addLast(index);}
return;
}
//有邊指向目前節點說明還有前驅節點，處理前驅節點
for(int i = 1;i <= ver;i++){
if(g[i][index] < Integer.MAX_VALUE) //有邊相連
helper(i);
}
//到這裡一定是所有的前驅節點都處理過了，是以隻要把目前節點加入隊列即可。
if(used[index] == 0){
used[index] = 1;
queue.addLast(index);
}
}
static void init(){
g = new int[ver+5][ver+5];
queue = new LinkedList<Integer>();
ingoing = new int[ver+5];
outgoing = new int[ver+5];
used = new int[ver+5];
for(int i=1;i<=ver;i++){
//初始S為空，Q為全部節點
for(int j=0;j<ver;j++)
g[i][j] = Integer.MAX_VALUE;
}
}
static void input(){
Scanner cin = new Scanner(System.in);
System.out.println("請輸入 點數 邊數");
ver = cin.nextInt();
edge = cin.nextInt();
int s,e,w;
init();
System.out.println("起點 終點");
for(int i=0;i<edge;i++){
s = cin.nextInt();
e = cin.nextInt();
g[s][e] = 1;
if(s != e){
ingoing[e] += 1;
outgoing[s] += 1;
}
}
}
static void print(){
System.out.println("拓撲排序結果：");
Iterator<Integer> iter = queue.iterator();
while(iter.hasNext()){
System.out.print(iter.next()+" ");
}
System.out.println();
}
public static void main(String[] args){
input();
tplgOrd();
print();
}
}
/*
請輸入 點數 邊數
9 10
起點 終點
1 2
2 4
2 3
5 3
5 6
6 7
3 7
1 4
8 4
9 9
拓撲排序結果：
1 2 8 4 5 3 6 7 9
*/
2. 強連通分量
有向圖 G = (V,E) 的強連通分量是一個最大節點集合C 包含于 V，對于該集合中的一對節點u和v來說，路徑u- --> v 和路徑 v --> u同時存在；也就是說節點u和節點v可以互相到達。
有一條很重要的性質，圖G與圖G_sup{T}(用sup代表上标)的強連通分量完全相同（後者表示G的轉置）。
僞代碼：
STRONGLY-CONNECTED-COMPONENTS(G)
1.call DFS(G) to compute times u.f for each vertex u
2.compute G_sup{T} //時間複雜度O(V+E)
3.call DFS(G_sup{T}), but in the main loop of DFS, consider the vertices in order of decreasing u.f
4.output the vertices of each tree in the depth-first formed in line3 as a separate strongly connected component
怎麼了解這個算法呢？我先用自己的語言來解釋一下。上面我們說到圖G與其轉置具有相同的強連通分量。我們從圖G中取出兩個連通分量C_i和C_j來看一下，首先要明确一點，C_i和C_j之間不可能同時有一條從C_i------>C_j和C_j---->C_i（或者反過來）的邊，因為如果那樣的話，C_i和C_j就不是兩個連通分量了。轉置後仍然是同樣的情況。換句話說，從C_i中的某一點開始進行DFS，不會發生通路到C中點并從其他邊傳回的情況，隻能原路傳回。那麼對于任何DFS路徑，先通路的連通分量中節點的u.f一定是大于後通路的連通分量中節點的u.f。上面所描述的就對應下面的定理
引理1： 設C和C'為有向圖G=(V,E)的兩個不同的強連通分量，設節點u,v in C，節點u',v' in C'，假定圖G包含一條從節點u到節點u'的路徑u-->u'，那麼圖G不可能包含一條從節點v'到v的路徑v'-->v。
引理2：設C和C’為有向圖G=(V,E)的兩個不同的強連通分量。假如存在一條邊(u,v) in E,這裡u in C,v in C'，則f(C) > f(C').
推論1：設C和C'為有向圖G=(V,E)的兩個不同的強連通分量，假如存在一條邊(u,v) in E_sup{T}，這裡u in C, v in C',則f(C) < f(C')。
其中，f(C)是集合C中所有節點裡最晚的完成時間。
定理：算法STRONGLY-CONNECTED-COMPONENTS能夠正确計算出有向圖G的強連通分量。
這個的證明過程我十分喜歡，提供了一種很好的證明算法正确性的方法，要仔細看一下。
證明：以算法第3行對G的轉置進行DFS時所發現的深度優先樹的棵數來進行歸納。假設，算法第3行所生成的前面k棵樹都是強連通分量。歸納證明的初始情況是k = 0時，歸納假設顯然成立。
歸納步，現在需要考慮第(k+1)棵樹。設樹的根節點為u，節點u處于強連通分量C中。根據我們在算法第3行選擇DFS搜尋根節點的方式，對于任意除C之外且尚未被通路的強連通分量C'來說，有u.f = f(C) > f(C')。根據歸納假設，在搜尋算法通路節點u的時刻，C中的所有節點都是白色的，根據白色路徑定理，C中其他的所有節點都是節點u在深度優先樹中的後代。而且，根據歸納假設和推論1，轉置圖G_sup{T}中所有從C發出的邊隻能是指向已經通路過的強連通分量。是以，除C以外的強連通分量中的節點不可能在對G_sup{T}進行深度優先搜尋時成為u的後代。是以，轉置圖G_sup{T}裡根節點為u的深度優先樹中的所有節點恰好形成一個強連通分量。
該算法的時間複雜度為theta(V+E)。