DFS深度優先搜尋
一路走到底再回頭，是連通分量與拓撲排序的基礎。
用在：遍歷資料夾、油漆桶填色、偵測循環依賴
01為什麼需要它
Finder 或 du 指令要算一個資料夾佔多少空間：進入子資料夾，算完它的大小再回到上一層加總，一路往下直到沒有子資料夾。
為什麼用它「進去、處理完、再回來」正是 DFS 的遞迴結構。樹狀的東西（檔案系統、DOM、JSON）幾乎都用 DFS 走。
點一下，整片連在一起的同色區域都被填色。影像處理的 flood fill、遊戲裡消除相連的同色方塊、地圖上數島嶼，都是找「連通區域」。
為什麼用它DFS 從一個點出發把能到的全部走完，走完的那一團就是一個連通分量。程式碼比 BFS 短，用遞迴幾行就寫完。
模組 A import B、B import C、C 又 import A，打包工具要在出事前發現這個環。Excel 公式互相參照、套件版本相依也一樣。
為什麼用它DFS 能區分「正在探索中」和「已完成」的節點。走到一個還在探索中的節點，就代表有環。BFS 做不到這個判斷。
看到這些關鍵字就想到它：連通區域、填色、有沒有環、所有路徑／所有組合、樹狀結構走訪、需要回溯。
02核心概念
DFS 挑一條路一直往深處走，走到沒路了才退回上一個岔路口，換另一條沒走過的路繼續。這種「先深入、再回頭」的順序，正好就是堆疊（Stack）後進先出的行為，所以最自然的寫法是遞迴：函式呼叫本身就是一個堆疊。
和 BFS 相比，DFS 不保證找到最短路徑，但它能記住「我是怎麼走到這裡的」，這條路徑資訊讓它成為偵測環、找連通分量、拓撲排序與列舉所有路徑的基礎。
每個節點會經歷三種狀態：未發現、探索中（已進入但鄰居還沒看完，正待在堆疊裡）、已完成（所有鄰居都處理完，已從堆疊彈出）。很多進階應用都靠這個區別，例如「探索中」的節點再被碰到一次，就表示圖裡有環。
03演算法步驟
- 1從起點呼叫
dfs(u)，把u標記為已發現，並記錄走訪順序。 - 2依序看
u的每個鄰居v：若v尚未發現，立刻遞迴呼叫dfs(v)，先把v那條路走完再回來看下一個鄰居。 - 3當
u的鄰居全部看完，dfs(u)返回，也就是回溯到呼叫它的節點。 - 4起點的
dfs返回時，所有從起點可達的節點都已走訪。若要走訪整張圖，對每個尚未發現的節點再呼叫一次，每呼叫一次就是一個連通分量。
04互動示範
同一張圖，同樣從 A 開始，鄰居按字母順序處理。留意堆疊怎麼長高又縮回，以及節點下方的走訪編號：和 BFS 的層次順序完全不同。
05程式碼
遞迴版最貼近概念；圖很深時可能超過遞迴深度限制，那時改用明確的堆疊（迭代版）。
def dfs(adj, start):
# adj: dict[node, list[node]]，回傳走訪順序
order = []
visited = set()
def go(u):
visited.add(u)
order.append(u)
for v in adj[u]:
if v not in visited:
go(v) # 先走完 v 這條路再看下一個鄰居
# 這裡是 u 的「完成」時刻（回溯點）
go(start)
return order
def dfs_iterative(adj, start):
# 用明確的堆疊取代遞迴，順序與遞迴版可能略有不同
order, visited = [], set()
stack = [start]
while stack:
u = stack.pop() # 從頂端取出
if u in visited:
continue
visited.add(u)
order.append(u)
for v in reversed(adj[u]): # 反向壓入，才會先處理第一個鄰居
if v not in visited:
stack.append(v)
return order06練習題
- LeetCode 695Max Area of IslandMedium
- LeetCode 133Clone GraphMedium
- LeetCode 797All Paths From Source to TargetMedium
- LeetCode 207Course ScheduleMedium
- LeetCode 547Number of ProvincesMedium