邊的分類（edge classification）

當深度優先搜尋執行時，它把圖切成一棵由發現邊構成的 DFS 樹，外加所有剩下的邊。美妙之處在於那些剩下的邊並非雜亂無章——每一條都依其兩端在樹中的位置落入少數幾種定義明確的類型，而知道一條邊的類型就告訴你關於圖結構的某件具體事情。「邊的分類」就是在每條邊被遇到時為它貼上標籤，是 DFS 幾乎免費產出的診斷讀數。

利用發現與完成時間戳，當 DFS 從 u 檢視一條邊 (u, v) 的當下，分類如下。若 v 未拜訪，它成為樹邊（用來發現 v 的那條邊）。若 v 已拜訪但仍「在堆疊上」——是 u 的祖先、其區間包含 u 的區間——它是回邊，由後代指向祖先。若 v 已完成且是 u 的後代（v 的區間巢狀於 u 之內，但 v 早先經由另一條路被抵達），它是前向邊。若 v 已完成且既非祖先也非後代（兩區間不相交），它是橫向邊，在兩條獨立分枝之間跳躍。你純粹從時間戳與一個「仍在堆疊上」的旗標就能判定身處哪種情況，所以分類不增加漸進成本：仍是 O(n + m)。

這些標籤是本領域其餘部分的原料。一條回邊恰是一個環的見證，因此「有沒有回邊？」就是環偵測。在有向無環圖中依定義沒有回邊，這正是拓樸排序得以可能的原因。前向邊與橫向邊只出現在有向 DFS（無向 DFS 只產生樹邊與回邊）。要記住的誠實提醒：這個分類是相對於某一次特定的 DFS 執行——不同的起點或鄰居順序可能把原本的橫向邊變成前向邊。不變且可信的是回邊的有無，因為那反映圖中真實的環，與你怎麼搜尋無關。