如果已經有一個圖儲存在記憶體裡面了，我們可以用哪些方式有系統地走遍這張圖呢？今天介紹的是大家耳熟能詳的深度優先搜尋（Depth First Search）。DFS 的發展與靈感其實來自於走迷宮問題，「如何有效率並且不出差錯地走出迷宮」。而這些想法在 1950 年代左右被應用到各式各樣的演算法中，尤其是 Robert Tarjan 在這段期間發表了許多驚心動魄的 DFS 應用，造福後世。
§3.1 DFS 演算法
在這邊幫大家快速複習一下 DFS 和相關的性質。首先我們會在每個點定義一個的狀態：「尚未走訪（白色，white）」、「走訪中（灰色，gray）」、「已結束走訪（黑色，black）」。每一個圖上的點在任意時刻都會是這三種狀態的其中之一。
而從一個指定節點進行深度優先搜尋的方法如下：
- $\text{DFS}(x):$
- 首先將該節點 $x$ 的狀態改為灰色。
- 考慮所有相連邊 $(x, y)\in E$，若另一頭的節點 $y$ 是白色，就遞迴執行 $\text{DFS}(y)$。
- 若所有相連邊的另一頭都已是灰色或黑色，則將節點 $x$ 狀態改為黑色。
DFS 樹
在 DFS 的過程中，如果我們把所有的走訪的節點 $y$，與呼叫 $\text{DFS}(y)$ 當下走訪的節點 $x$ 連起來，會得到一棵樹。這樣的樹我們把它稱之為 DFS 樹。
§3.2 邊的分類
不難證明，對某個圖 $G$ 上面的點 $v\in V$，在呼叫 $\text{DFS}(v)$ 後，與 $v$ 同屬相同連通塊的所有邊都會被看過 1 次（無向邊的話會從兩個方向各自看過一次，因此總共會被看過 2 次）。我們可以對這些邊 $(x, y)$ 依照被發現當下的特性進行歸類：
- 如果 $y$ 是白色，那這條邊會被稱為 tree-edge（因為會緊接著呼叫 $\text{DFS}(y)$，所以這條邊會在 DFS 樹上）。
- 如果 $y$ 是灰色，那這條邊會被稱為 back-edge。
- 如果 $y$ 是黑色、而且 $x$ 是 $y$ 在 DFS 樹上面的祖先，那麼這條邊會被稱為 forward-edge。
- 如果 $y$ 是黑色，但是 $x$ 並非 $y$ 在 DFS 樹上的祖先，那麼這條邊會被稱為 cross-edge。