簡介
深度優先搜索（Depth-First-Search）是搜索算法的一種。是沿着樹的深度遍曆樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索将回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點并重複以上過程，整個進程反複進行直到所有節點都被訪問為止。屬于盲目搜索。
深度優先搜索是一種在開發爬蟲早期使用較多的方法。。在一個HTML文件中，當一個超鍊被選擇後，被鍊接的HTML文件将執行深度優先搜索，即在搜索其餘的超鍊結果之前必須先完整地搜索單獨的一條鍊。深度優先搜索沿着HTML文件上的超鍊走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鍊。當不再有其他超鍊可選擇時，說明搜索已經結束。優點是能遍曆一個Web 站點或深層嵌套的文檔集合；缺點是因為Web結構相當深,，有可能造成一旦進去，再也出不來的情況發生。
事實上,深度優先搜索屬于圖算法的一種,英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節點隻能訪問一次。
深度優先搜索是圖論中的經典算法，利用深度優先搜索算法可以産生目标圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明“深度優先搜索算法”，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎。
方法技巧
每次深度優先搜索的結果必然是圖的一個連通分量.深度優先搜索可以從多點發起.如果将每個節點在深度優先搜索過程中的"結束時間"排序(具體做法是創建一個list,然後在每個節點的相鄰節點都已被訪問的情況下,将該節點加入list結尾,然後逆轉整個鍊表),則我們可以得到所謂的"拓撲排序",即topological sort.
當然,當人們剛剛掌握深度優先搜索的時候常常用它來走迷宮.事實上我們還有别的方法,那就是廣度優先搜索(BFS).狀态（state):狀态是制問題求解過程中每一步的狀況。
算符（operater）算符是把問題從一種狀态變換到另一種狀态的方法代号。算符的屈指範圍就是搜索的範圍。（一般設為局部變量)。
節點（node）:用來表明狀态特征及相關信息。
效率問題
作為搜索算法的一種，DFS對于尋找一個解的NP（包括NPC）問題作用很大。但是，搜索算法畢竟是時間複雜度是O(n!)的階乘級算法，它的效率比較低，在數據規模變大時，這種算法就顯得力不從心了。
關于深度優先搜索的效率問題，有多種解決方法。最具有通用性的是剪枝（prunning），也就是去除沒有用的搜索分支。有可行性剪枝和最優性剪枝兩種。此外，對于很多問題，可以把搜索與動态規劃（DP,dynamic programming)、完備匹配（匈牙利算法）等高效算法結合。
算法詳解
首先選定圖的類别（有向圖、無向圖），再選定圖的存儲結構，根據輸入的頂點或者邊建立圖；并把相應的鄰接表或者鄰接矩陣輸出；根據已有的鄰接矩陣或鄰接表用遞歸方法編寫深度優先搜索遍曆算法，并輸出遍曆結果；圖的深度遍曆原則：
1 如果有可能，訪問一個領接的未訪問的節點，标記它，并把它放入棧中。
2 當不能執行規則 1 時，如果棧不為空，則從棧中彈出一個元素。
3 如果不能執行規則 1 和規則 2 時，則完成了遍曆。
代碼中的圖使用的是Graph 圖－鄰接矩陣法 來表示，其他的表示法請見：Graph 圖－鄰接表法
代碼中的Stack為輔助結構，用來記載訪問過的節點。棧的詳細描述可以見：ArrayStack 棧 ，LinkedStack 棧 。
Vertex表示圖中的節點，其中包含訪問，是否訪問，清除訪問标志的方法。 Graph.main：提供簡單測試。代碼可以以指定下标的節點開始作深度遍曆。 代碼比較簡單，除了Graph.dsf(int i)深度優先遍曆算法外沒有過多注釋。
搜索過程
搜索原理
正如算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能“深”地搜索圖。在深度優先搜索中，對于最新發現的頂點，如果它還有以此為起
點而未探測到的邊，就沿此邊繼續漢下去。當結點v的所有邊都己被探尋過，搜索将回溯到發現結點v有那條邊的始結點。這一過程一直進行到已發現從源結點可達的所有結點為止。如果還存在未被發現的結點，則選擇其中一個作為源結點并重複以上過程，整個進程反複進行直到所有結點都被發現為止。
和寬度優先搜索類似，每當掃描已發現結點u的鄰接表從而發現新結點v時，深度優先搜索将置v的先輩域π[v]為u。和寬度優先搜索不同的是，前者的先輩子圖形成一棵樹，而後者産生的先輩子圖可以由幾棵樹組成，因為搜索可能由多個源頂點開始重複進行。因此深度優先搜索的先輩子圖的定義也和寬度優先搜索稍有不同： Gπ=(V,Eπ),Eπ={(π[v],v)∈E:v∈V∧π[v]≠NIL}
深度優先搜索的先輩子圖形成一個由數個深度優先樹組成的深度優先森林。Eπ中的邊稱為樹枝。
和寬度優先搜索類似，深度優先在搜索過程中也為結點着色以表示結點的狀态。每個頂點開始均為白色，搜索中被發現時置為灰色，結束時又被置成黑色(即當其鄰接表被完全檢索之後)。這一技巧可以保證每一頂點搜索結束時隻存在于一棵深度優先樹上，因此這些樹都是分離的。
除了創建一個深度優先森林外，深度優先搜索同時為每個結點加蓋時間戳。每個結點v有兩個時間戳：當結點v第一次被發現(并置成灰色)時記錄下第一個時間戳d[v]，當結束檢查v的鄰接表時(并置v為黑色)記錄下第二個時間截f[v]。許多圖的算法中都用到時間戳，他們對推算深度優先搜索進行情況是很有幫助的。
過程記錄
下列過程DFS記錄了何時在變量d[u]中發現結點u以及何時在變量f[u]中完成對結點u的檢索。這些時間戳為1到2|V|之間的整數，因為對每一個v中結點都對應一個發現事件和一個完成事件。對每一頂點u，有 d[u](1) 在時刻d[u]前結點u為白色，在時刻d[u]和f[u]之間為灰色，以後就變為黑色。 下面的僞代碼就是一個基本的深度優先搜索算法，輸人圖G可以是有向圖或無向圖，變量time是一個全局變量，用于記錄時間戳。
procedure DFS(G); - begin
- 1 for 每個頂點u∈V[G] do
- begin
- 2 color[u]←White;
- 3 π[u]←NIL;
- end;
- 4 time←0;
- 5 for 每個頂點u∈V[G] do
- 6 if color[u]=White
- 7 then DFS_Visit(G,u);
- end; -
- procedure DFS_Visit(G,u);
- begin
- 1 color[u]←Gray; Δ白色結點u已被發現
- 2 d[u]←time←time+1;
- 3 for 每個頂點v∈Adj[u] do Δ探尋邊(u,v)
- 4 if color[v]=White
- then begin
- 5 π[v]←u;
- 6 DFS_Visit(G,v);
- end;
- 7 color[u]←Black; Δ完成後置u為黑色
- 8 f[u]←time←time+1;
- end;
被算法探尋到的邊要麼為陰影覆蓋 (如果該邊為樹枝)，要麼成虛線形式 (其他情況)。對于非樹枝的邊，分别标明B(或F)以表示反向邊、交叉邊或無向邊。用發現時刻Z完成時刻的形式對結點加蓋時間戳。
深度優先搜索算法DFS在有向圖上的執行過程
過程DFS執行如下。第1-3行把所有結點置為白色，所有π域初始化為NIL。第4行複位全局變量time，第5-7行依次檢索V中的結點，發現白色結點時，調用DFS_Visit去訪問該結點。每次通過第7行調用DFS_Visit時，結點u就成為深度優先森林中一棵新樹的根，當DFS返回時，每個結點u都對應于一個發現時刻d[u]和一個完成時刻f[u]。 每次開始調用DFS_Visit(u)時結點u為白色，第1行置u為灰色，第2行使全局時間變量增值并存于d[u]中，從而記錄下發現時刻d[u]，第3-6行檢查和u相鄰接的每個頂點v，且若v為白色結點，則遞歸訪問結點v。在第3行語句中考慮到每一個結點v∈Adj[u]時，可以說邊(u,v)被深度優先搜索探尋。最後當以u為起點的所有邊都被探尋後，第7-8行語句置u為黑色并記錄下完成時間f[u]。
算法DFS運行時間的複雜性如何？DFS中第1-2行和5-7行的循環占用時間為O(V),這不包括執行調用DFS_Visit過程語句所耗費的時間。事實上對每個頂點v∈V，過程DFS_Visit僅被調用一次，因為DFS_Visit僅适用于白色結點且過程首先進行的就是置結點為灰色，在DFS_Visit(v)執行過程中，第3-6行的循環要執行|Adj[v]|次。因為∑v∈V|Adj[v]|=θ(E)，因此執行過程DFS_Visit中第2-5行語句占用的整個時間應為θ(E)。所以DFS的運行時間為θ(V+E)
