從一圈圈的環到一頭栽下去
前一篇給了你廣度優先搜尋，它從來源以一圈圈擴大的環往外散開：先是所有距離一條邊的頂點，再來是距離兩條邊的，依此類推。深度優先搜尋則把這種性情完全顛倒過來。深度優先搜尋不耐著性子把附近的東西全探一遍，而是認定一個鄰居就一頭栽下去、能多深就多深，沿著一條又一條邊鑽進未知，直到走到一個沒有任何未拜訪鄰居的頂點。到那一刻它才退回一步、試下一個選項。廣度優先搜尋像個謹慎的測量員；深度優先搜尋則像個一路直走進洞、直到隧道到底才罷休的探險家。
在機制上，與廣度優先搜尋唯一的差別，是那個存著「下一步要去哪」的資料結構。廣度優先搜尋用佇列（先進先出），所以最早被發現的前緣頂點會最先被探，產生一圈圈的環。深度優先搜尋用堆疊（後進先出）——最自然的就是遞迴的呼叫堆疊——所以最新被發現的頂點會最先被探，產生一次下潛。把佇列換成堆疊，整個搜尋的個性就反轉了。其餘的一切，掃描鄰居的鄰接串列、以及阻止你重訪的「已拜訪」標記，全都和原本一模一樣。
DFS(u):
color[u] = gray; time = time+1; disc[u] = time # entering u
for each neighbor v of u:
if color[v] == white: # v never seen -> tree edge
parent[v] = u
DFS(v)
color[u] = black; time = time+1; fin[u] = time # leaving u深度優先樹與括號結構
就像廣度優先搜尋替每個頂點記下父節點、建出一棵廣度優先樹一樣，深度優先搜尋每次踏進一個全新頂點時也記下父節點，建出一棵深度優先樹（若圖不連通、而你從每個未拜訪頂點重新啟動搜尋，就會是一片森林）。但深度優先樹往往又高又細——一條條向下延伸的長路徑——而廣度優先樹則又矮又茂密。那個形狀正是重點：它捕捉了搜尋下潛與浮上的順序，而這順序由每個頂點的兩個時間戳記錄下來：它的發現時間（深度優先搜尋第一次把它塗灰時）與完成時間（深度優先搜尋把它塗黑並返回時）。
這些時間戳遵守一條優美而剛硬的規則，叫做括號結構。想像深度優先搜尋發現 u 時寫下一個左括號「(u」、完成 u 時寫下一個右括號「u)」。因為深度優先搜尋總是把一個頂點完全處理完才返回它的父節點，這些括號永遠完美地巢狀——像「( ( ) ( ) )」——絕不會像「( [ ) ]」那樣交叉。具體地說：對任意兩個頂點 u 與 v，它們的「發現—完成」區間，要嘛完全不相交，要嘛其中一個完全巢狀在另一個之內。而這種巢狀並非巧合——v 的區間落在 u 的區間之內，恰好就在 v 是 u 在深度優先樹中的後代時。
四種邊
深度優先搜尋的真本事就在這裡。搜尋進行時，它檢視的每一條邊都恰好落入四類之一，而落入哪一類，完全由你看它那一刻另一端點的顏色決定。這種歸類叫做邊的分類，學會讀它，就把深度優先搜尋從一個拜訪圖的方法，變成一個理解圖的結構的方法。樹邊是深度優先搜尋用來發現一個全新頂點的邊——另一端是白色。這些恰好就是深度優先樹的邊，每棵樹至多 n-1 條。
另外三種是「剩餘」（非樹）邊，靠另一端點相對於你的位置來區分。回邊（後向邊）指向一個灰色頂點——一個還開著、在你當前路徑上的祖先；你剛剛繞回了自己的足跡。前向邊指向一個你已經處理完的黑色後代（你用一條捷徑又抵達了它）。交叉邊指向一個既非祖先也非後代的黑色頂點——一棵不同的子樹，或同一棵樹裡較早完成的部分。可靠的判定靠時間戳：比較兩端點的 disc 與 fin，不必畫出樹就能告訴你身處哪一種情況。
為什麼回邊就意味著環
邊的分類最重要的回報，是這條乾淨的定理：一個有向圖有環，若且唯若深度優先搜尋找到一條回邊。那個「若且唯若」正是它之所以是一個演算法、而非一個一廂情願的啟發法的原因，所以讓我們看看兩個方向為何都成立——這就是環偵測，它跑在與搜尋本身相同的 O(n + m) 時間裡，其中 m 是邊數。
- 簡單方向——回邊必然造出一個環。一條回邊 (u, v) 從 u 指向一個仍是灰色的祖先 v，也就是說 v 在當前路徑上還開著。所以深度優先樹裡早已有一條從 v 沿樹邊向下到 u 的路徑；加上這條從 u 到 v 的回邊，那條路徑就閉合成一個環。沒有一條回邊是清白的。
- 困難方向——每個環都製造一條回邊。假設圖裡有一個環。在它的頂點中，令 w 是深度優先搜尋最先發現的那一個。當 w 還是灰色時，深度優先搜尋會（直接地、或透過它的後代）探索這個環，最終檢視到由環上前一個頂點進入 w 的那條邊。在那一刻 w 仍是一個開著的祖先——灰色——所以那條邊被歸為回邊。
- 於是「存在環」與「出現回邊」在邏輯上等價。要把它變成程式碼，你甚至不需要完整的時間戳：維護一個灰色集合（當前在遞迴堆疊上的頂點），一旦掃描到某條邊的另一端是灰色，就立刻回報一個環。整個偵測器就這麼多。
這裡要標記一個常見的陷阱：在無向圖裡，判定幾乎相同，但你必須忽略直接的父節點。因為一條無向邊會從兩端各被掃描一次，你剛剛用來進入某頂點的那條邊，否則看起來就會像一條指回自己父節點的回邊，而錯誤地大喊「有環」。跳過那一條邊，「回邊意味著環」的規則就又成立了——而且無向圖的深度優先搜尋更為清爽，因為只會出現樹邊與回邊，絕不會有前向邊或交叉邊。
邊的種類解鎖了什麼
讀邊本身不是目的；它是一把萬能鑰匙。一個有向圖裡不存在任何回邊，意味著沒有環，也就是說這圖是個有向無環圖（DAG）——而下一篇會證明，按遞減的完成時間列出頂點，就會得到一個合法的拓樸排序，因為一個頂點總是在所有從它可達的頂點之後才完成。交叉邊與樹邊合起來讀，也讓單趟深度優先搜尋掃描就能標記出一個無向圖的每個連通分量：每次從一個全新的白色頂點重新啟動搜尋，就開啟了一個新的分量。
這一級裡更深的結構性結果，靠的是同一桶燃料。強連通分量靠兩趟深度優先搜尋找出，其正確性是一個關於完成時間的括號結構論證。割點與橋靠單趟深度優先搜尋找出，方法是替每個頂點追蹤「任何回邊能往上爬到的最早祖先」——同樣是一個純粹關於回邊的問題。一再出現、值得你帶著往上爬的教訓是：深度優先搜尋不只是像一缸燃料那樣抵達每個頂點——它的發現與完成時間編碼了圖的巢狀結構，而幾乎每一個快速的圖演算法，都是一種讀取那份編碼的方法。
最後說一個關於代價與限制的誠實提醒。深度優先搜尋和廣度優先搜尋一樣，跑在 O(n + m) 時間，並用 O(n) 的額外空間存顏色、時間戳與遞迴堆疊——這也是它主要的實務注意點：在一個有百萬頂點長路徑的圖上，遞迴可能撐爆呼叫堆疊，所以很深的深度優先搜尋常被改寫成用顯式堆疊。並且記住，深度優先搜尋回答的是可達性與結構，不是距離：和廣度優先搜尋不同，它不會給出以邊數計的最短路徑，因為它會先一頭栽進一條長路線，才考慮一條較短的平行路線。挑搜尋法來配合你的問題。