DFS 樹（the DFS tree）

深度優先搜尋探索時像一個決心把每條走廊走到死路才回頭的人：從當前頂點沿一條未探索的邊潛入，再從那裡潛入，越鑽越深，直到碰到一個沒有未探索鄰居的頂點，此時退回一步、試下一條走廊。若你只保留 DFS 用來發現新頂點的那些邊，便得到一棵以起點為根的樹——DFS 樹——它捕捉了搜尋那深而蜿蜒的形狀。

機制上，DFS 使用堆疊，通常就是遞迴的呼叫堆疊。拜訪 u：標記 u，然後對每個鄰居 v，若 v 未拜訪，就把邊 u->v 記為樹邊並遞迴進 v；遞迴返回後，繼續處理 u 的下一個鄰居。讀這棵樹的乾淨方式是給每個頂點兩個時間戳：第一次進入它時的發現時間，與最終離開它時的完成時間。它們服從一種巢狀（括號）結構：對任兩個頂點，其區間 [發現, 完成] 要嘛完全巢狀地一個套在另一個內、要嘛完全不相交——絕不部分重疊。這種巢狀正是祖先-後代關係的確切指紋：u 是 v 在 DFS 樹中的祖先，恰當 v 的區間嚴格落在 u 的區間之內。這一個事實就是拓樸排序、強連通分量、關節點與橋背後的引擎。

DFS 樹之所以重要，是因為原圖的邊與這棵樹的關係揭露了深層結構：從一個頂點通往它自己某個樹祖先的邊（回邊）暴露出環，而在有向圖中，完成時間的順序給出一個有向無環圖的有效拓樸排序。配上鄰接串列它跑在 O(n + m)。誠實的提醒：DFS 樹並不唯一——換你先探索哪個鄰居、或從哪個頂點出發，就得到不同的樹。穩健的是括號巢狀及它導出的邊分類；下游演算法倚賴的是這些，而非樹的確切形狀。