圖
深度優先搜尋
深度優先搜尋（DFS）的探索方式是：沿著一條路盡可能往深處走，走不動了再回頭。這就像在紙上走迷宮：順著一條走廊一直走到盡頭，只有撞上死路時，才退回上一個岔口、換一個方向再試。DFS 會一條路走到底，然後回溯。
它天然的引擎是一個堆疊（後進先出）——而拿到一個堆疊最簡單的辦法就是遞迴，遞迴用的正是程式自己的呼叫堆疊。到達某頂點後先標記它已造訪，然後遞迴進入它第一個未造訪的鄰居，再進入那個鄰居第一個未造訪的鄰居，依此類推；當一個頂點再沒有未造訪的鄰居時，遞迴就返回（回溯）到上一個頂點。和 BFS 一樣，正是「標記已造訪」阻止了環造成的無限迴圈。也可以用一個顯式的 std::stack 把 DFS 寫成迭代形式。
DFS 同樣對每個頂點造訪一次、對每條邊檢查一次，在鄰接表上為 O(V + E) 時間。它不求最短路徑，但這種「先把當前分支走完」的深入順序，非常適合偵測環、求連通分量、列舉所有方案，以及對有向無環圖做拓撲排序等任務。
vector<bool> seen(n, false);
void dfs(int v) {
seen[v] = true; // visit v
for (int nb : adj[v])
if (!seen[nb]) dfs(nb); // dive deeper
} // return = backtrack每次呼叫都深入一個鄰居；返回就是回溯的那一步。
在很深的圖上，遞迴式 DFS 可能撐爆呼叫堆疊；改用顯式堆疊可以避開這個限制。
又稱
另見