樹邊、回邊、前向邊與橫向邊（tree, back, forward and cross edges）

跑一趟深度優先搜尋，圖的每條邊相對於 DFS 樹最終都扮演四種角色之一。把這棵樹想成搜尋建立的家族世系——父母發現子女，子女再發現孫輩。每條剩下的邊不是往家族線上方回去、就是往下、或橫向通往另一條分枝。這四種角色——樹邊、回邊、前向邊、橫向邊——是談論圖的邊如何相對於探索它的搜尋而存在的完整詞彙。

以下是這四種，各自所標誌的結構事實。樹邊 u->v 是 DFS 用來第一次發現 v 的邊；單是樹邊就構成 DFS 樹。回邊由樹中下方的頂點 u 通往 u 的某個祖先 v（其區間仍開著、v 仍在遞迴堆疊上）——而回邊正是環存在的確切憑證，因為從 v 往下到 u 的樹路徑加上回邊 u->v 便閉合成一個圈。前向邊由祖先 u 通往一個已完成的真後代 v，而 v 早先是經由更長的樹路徑被發現的——它是一條往樹下方的捷徑。橫向邊連接位於不同分枝（或不同 DFS 樹）的兩個頂點，且彼此都不是對方的祖先；在時間戳的圖像裡，u 發現 v 已完成且區間不相交。一條乾淨的口訣：無向圖中只會出現樹邊與回邊；前向邊與橫向邊需要方向。

為何要把這些分清楚？因為本領域的整套工具都用它們來表述。環偵測是「有沒有任何回邊存在？」。有向無環圖恰是在 DFS 下沒有回邊的有向圖，這正是拓樸排序行得通的原因。強連通分量演算法與關節點偵測都倚賴把一個頂點與透過回邊可達的最低祖先做比較。誠實的細微之處：若你從不同頂點重啟 DFS、或以另一種順序掃描鄰居，哪些是前向邊、哪些是橫向邊可能翻轉——這些標籤是相對於執行的。唯一屬於圖本身的標籤是回邊的存在，因為無論搜尋怎麼被引導，它都對應一個真正的環。