陶爾揚演算法

1. DFS的搜索的過程

當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是一種在開發爬蟲早期使用較多的方法。在一個HTML文件中，當一個超鏈被選擇後，被鏈接的HTML文件將執行深度優先搜索，即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。優點是能遍歷一個Web 站點或深層嵌套的文檔集合；缺點是因為Web結構相當深,，有可能造成一旦進去，再也出不來的情況發生。
事實上,深度優先搜索屬於圖演算法的一種,英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節點只能訪問一次.
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明「深度優先搜索演算法」，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.
正如演算法名稱那樣，深度優先搜索所遵循的搜索策略是盡可能「深」地搜索圖。在深度優先搜索中，對於最新發現的頂點，如果它還有以此為起點而未探測到的邊，就沿此邊繼續漢下去。當結點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]<f[u]
(1) 在時刻d[u]前結點u為白色，在時刻d[u]和f[u]之間為灰色，以後就變為黑色。 下面的偽代碼就是一個基本的深度優先搜索演算法，輸人圖G可以是有向圖或無向圖，變數time是一個全局變數，用於記錄時間戳。
procere 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; -
- procere 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;
- 圖2說明了DFS在圖1所示的圖上執行的過程。被演算法探尋到的邊要麼為陰影覆蓋 (如果該邊為樹枝)，要麼成虛線形式 (其他情況)。對於非樹枝的邊，分別標明B(或F)以表示反向邊、交叉邊或無向邊。我們用發現時刻Z完成時刻的形式對結點加蓋時間戳。
圖2 深度優先搜索演算法DFS在有向圖圖1上的執行過程
過程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)。

2. 深度優先演算法的定義

深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。是沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。屬於盲目搜索。
深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。
因發明「深度優先搜索演算法」，霍普克洛夫特與陶爾揚共同獲得計算機領域的最高獎：圖靈獎.