🎯 什麼情境該想到我
當你「要走遍整張圖、找環、找連通分量、或做回溯」的時候。
★ DFS 的威力不在「走訪」本身，而在它走訪時產生的時間戳與邊的分類——環偵測、拓撲排序、強連通分量全都建立在這上面。
⚙️ 怎麼用（機制與應用）
運作機制：一條路走到底，走不動了再回頭
// 遞迴版（好寫）
func dfs(adj [][]int, u int, visited []bool) {
visited[u] = true
// 前序：進入 u 時做的事
for _, v := range adj[u] {
if !visited[v] {
dfs(adj, v, visited)
}
}
// ★ 後序：離開 u 時做的事 —— 拓撲排序與強連通分量靠這裡
}
// 迭代版（深圖必備，避免爆堆疊）
func dfsIter(adj [][]int, s int) {
visited := make([]bool, len(adj))
stack := []int{s}
for len(stack) > 0 {
u := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if visited[u] { continue } // ★ 出堆疊時才檢查（同一點可能被推入多次）
visited[u] = true
for _, v := range adj[u] {
if !visited[v] { stack = append(stack, v) }
}
}
}★ 迭代版和 BFS 的差別只有一行：
stack[len-1]+ pop 尾端 vsq[0]+ pop 頭部。
但注意 DFS 迭代版要在「出堆疊」時檢查 visited，BFS 要在「入佇列」時標記——兩者不同（見 廣度優先搜尋）。
★ 三色標記：環偵測的正確做法
白 (0)：還沒訪問
灰 (1)：★ 正在遞迴中（在當前的 DFS 路徑上）
黑 (2)：已完全處理完（它的所有後代都走完了）
func hasCycle(adj [][]int) bool {
color := make([]int, len(adj))
var dfs func(int) bool
dfs = func(u int) bool {
color[u] = 1 // 灰
for _, v := range adj[u] {
if color[v] == 1 { return true } // ★ 撞到灰色 = 回到當前路徑上 = 有環
if color[v] == 0 && dfs(v) { return true }
}
color[u] = 2 // 黑
return false
}
for u := range adj {
if color[u] == 0 && dfs(u) { return true }
}
return false
}★ 為什麼不能只用
visited布林值：
撞到一個「已訪問」的節點，可能是回到當前路徑上（有環），
也可能是走到另一條已經處理完的分支（沒有環）。
布林值分不出這兩種情況——必須用三色。（無向圖例外：無向圖只要記住「父節點」，撞到非父的已訪問節點就是環。）
邊的四種分類（有向圖）
DFS 把每條邊分成四類，這是很多演算法的理論基礎：
| 類型 | 指向 | 意義 |
|---|---|---|
| 樹邊 | 白色節點 | DFS 樹的一部分 |
| ★ 回邊（back edge） | 灰色節點 | ★ 有環的充要條件 |
| 前向邊 | 黑色後代 | — |
| 橫向邊 | 黑色非後代 | — |
有向圖有環 ⟺ DFS 中存在回邊。 這就是三色標記的理論依據。
主要應用
| 應用 | 關鍵 |
|---|---|
| 環偵測 | 三色標記（見上） |
| 拓撲排序 | ★ 後序完成時間的逆序就是拓撲序 |
| 連通分量（無向） | 對每個未訪問節點各跑一次 DFS |
| ★ 強連通分量（有向） | Tarjan（一次 DFS + low-link）或 Kosaraju（兩次 DFS） 用途：找出模組間的循環依賴、縮點 |
| 橋與割點 | Tarjan 的 low-link——找出「拿掉就會斷開」的邊／點 |
| 回溯搜尋 | N 皇后、數獨、排列組合——DFS + 撤銷狀態 |
複雜度
| 時間 | |
| 空間 | —— ★ 遞迴深度最差是 （一條長鏈） |
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ 遞迴會爆堆疊。Go 的 goroutine 堆疊會自動成長（預設上限 1 GB），所以比 C 耐操，
但深度百萬級的圖仍可能爆。深度不可控時用迭代版。 - ★ 不保證最短路。DFS 第一次到達某節點時走的不一定是最短路 → 最短路用 廣度優先搜尋。
- 環偵測要用三色，不能只用 visited（見上）。這是最常見的錯誤。
- 回溯時要記得「撤銷」狀態：
path = append(path, u) dfs(...) path = path[:len(path)-1] // ★ 漏掉這行是回溯題最常見的 bug - 無向圖的環偵測要排除父節點，否則
u → v → u會被誤判成環。 - 不連通的圖要對每個未訪問節點都起一次 DFS，只從一個點出發會漏掉其他分量。