環偵測（cycle detection）

一個環是一條繞回起點卻不回頭重走任何一步的路徑——穿過圖的一趟來回。問它是否存在是個基本而出奇有用的問題：一張有環的依賴圖意味互相永遠等待的任務（死鎖）、一個有環的建置系統無法決定編譯順序，而一張完全沒有環的圖（無向時是森林、有向時是 DAG）享有特殊、較容易的結構。環偵測就是判定圖是否含有環，而圖搜尋在線性時間內回答它。

深度優先搜尋藉由留意一種洩漏天機的邊來偵測環。對無向圖：跑 DFS，若你曾抵達一個已拜訪、且不是你來時所經父節點的頂點，你就找到了一條回邊，而回邊閉合一個環（從那個祖先往下到你的樹路徑，加上那條回邊）。「不是父節點」這個條件很重要，因為在無向圖中，你剛走過來的那條邊否則看起來會像一個長度為二的環。對有向圖規則更銳利：環存在，恰當 DFS 找到一條通往目前仍在遞迴堆疊上（仍在處理中）的頂點的邊——所謂的灰色頂點。抵達一個已完成（已完全探索）的頂點沒問題、不代表有環；只有通往仍開著的東西的邊才代表。對有向圖一個乾淨的替代法是嘗試拓樸排序：它成功，當且僅當沒有環，而它的失敗精準定位環的部分。這些全都跑在 O(n + m)。

除了是非題之外，環偵測支撐作業系統與資料庫中的死鎖偵測、驗證一張依賴或建置圖是無環的、找出負權環（需額外機制），以及在執行要求無環的演算法之前確認圖是樹或 DAG。兩個誠實的告誡。第一，無向與有向的測試確實不同——有向規則需要在堆疊（灰色）的檢查，把無向的「已拜訪但非父節點」測試天真地套用到有向圖上會回報假的環。第二，對一個特殊的結構化情境——在函數圖或鏈結串列中偵測環，其中每個節點恰有一個後繼——有一個美妙的常數空間技巧（弗洛伊德的龜兔雙指標法），不需儲存拜訪標記；但對一般圖而言，DFS 的回邊測試才是標準工具。