一條路走到底,撞牆再回頭。用堆疊或遞迴,是回溯與拓樸排序的基礎。
堆疊 / 遞迴當引擎 —— 一直往深處走,把「還沒試的分岔」記在堆疊上。
走到死路就回溯 —— 沒有新鄰居可走,就退回上一個分岔,換一條沒走過的。
visited 一樣要記 —— 避免重複、避免在有環的圖裡繞不完。
不保證最短 —— DFS 找到的是「一條」路,不是最短那條(要最短用 BFS)。
遞迴版 —— 最簡潔:函式自己呼叫自己,「回溯」就是 return 回上一層。底層用的正是程式的呼叫堆疊。
迭代版 —— 自己開一個 list 當堆疊,pop 最後放進去的。資料很深時避免遞迴爆掉(RecursionError)。
兩種等價 —— 把 BFS 的佇列換成堆疊,就從 BFS 變 DFS(範例 10)。
沿一條路一直走,撞牆就退回上一個路口,換一條沒走過的繼續 —— 這就是回溯。
沿一根樹枝爬到底端的葉子,再退回岔口爬另一根,直到爬遍。
打開一個資料夾就一直往裡點,點到最底再退回上一層看別的。
同款迷宮,這次看 DFS 怎麼走。它依「右→下→左→上」的順序一路鑽到底:琥珀是目前這條路(堆疊)、淡綠是走過但發現是死路、退回來的格子。注意它一開始往右鑽進死角,撞牆後回溯再換方向 —— 這正是 BFS 的「水波」沒有的行為。
從 DFS 遞迴 / 迭代、迷宮找路、回溯框架,到島嶼數量、偵測環、拓樸排序、全排列。
❌ 拿 DFS 找最短路 —— DFS 不保證最短。要最短用 BFS(不加權)或 Dijkstra(加權)。
❌ 遞迴太深爆掉 —— Python 預設遞迴上限約 1000,資料很深會 RecursionError,改用迭代堆疊或調高上限。
❌ 回溯忘了收回 —— 選一步遞迴後若失敗,一定要 pop 收回,不然狀態會髒掉、答案全錯。
❌ 忘了 visited —— 有環的圖會無限鑽。
把答案打到對話裡,我幫你對。