Learning Objectives
- 用遞迴寫出深度優先搜尋（DFS），並對照呼叫樹說明它「先走到底再回頭」
- 用自己的堆疊改寫成迭代版 DFS，說明為什麼鄰居要反著放
- 比較同一張圖上 BFS 與 DFS 的拜訪順序，知道各自適合的問題
- 用白、灰、黑三種顏色偵測有向圖裡的環，分辨灰色與黑色的差別
- 用 Kahn 演算法（入度與佇列）做拓撲排序，並用它判斷有沒有環
一路走到底，再回頭
走迷宮時，很多人會用這個方法：沿著一條路一直走，走到死路就退回上一個岔路口，換另一條沒走過的路。 這就是深度優先搜尋（DFS，depth-first search）。
上一課的 BFS 像水波，一層一層往外擴散；DFS 則是先往深處鑽，鑽到底才回頭。兩種走法都會走遍起點走得到的每個節點，差別在順序，而順序決定了它們各自擅長的問題：
| 問題 | 適合的走法 |
|---|---|
| 無權重圖的最短路徑、最少步數 | BFS |
| 有向圖有沒有環 | DFS |
| 課程先修、工作排程的先後順序（拓撲排序） | DFS 或 Kahn 演算法 |
| 走遍所有節點、數連通元件 | 兩種都可以 |
這一課先寫 DFS，再用它偵測環，最後解決「先修課要怎麼排」的問題。
DFS 用遞迴寫最自然
DFS 的定義本身就是遞迴的：
拜訪 u：標記 u 已拜訪；對 u 的每個鄰居 v，如果 v 還沒拜訪，就拜訪 v。
「拜訪 v」會一路往下，等 v 底下能走的都走完、函式回傳了，才輪到 u 的下一個鄰居。
這正是第 05 課的遞迴：每呼叫一次 dfs，呼叫堆疊就多一層；函式回傳就是「退回上一個岔路口」。
def dfs(adj, u, visited, order):
visited[u] = True
order.append(u)
for v in adj[u]:
if not visited[v]:
dfs(adj, v, visited, order)
下面用的是上一課 BFS 範例的同一張圖，可以直接比較兩種順序。
遞迴 DFS：看呼叫樹怎麼長
右邊的呼叫樹是一條很深的鏈：dfs(0) 呼叫 dfs(1)、dfs(1) 呼叫 dfs(3)……一路到 dfs(6)，因為每次都先往第一個還沒拜訪的鄰居走到底。拜訪順序是 0 1 3 2 4 5 6，上一課的 BFS 是 0 1 2 3 4 5 6。呼叫樹的形狀就是 DFS 樹：每條呼叫關係對應圖上的一條邊。
不用遞迴：自己準備一個堆疊
遞迴版很短，但有一個實際的限制：呼叫堆疊的深度有上限。Python 預設大約 1,000 層，
一張串成一直線、有 10 萬個節點的圖，遞迴 DFS 會直接出錯（RecursionError）；C++、Java 的上限比較高，但一樣會用完。
解法是把「呼叫堆疊」換成自己管理的堆疊（stack，第 10 課）：
- 堆疊裡先放起點
- 取出堆疊頂端的節點 u；如果已經拜訪過就跳過
- 標記 u、記進順序，把 u 還沒拜訪的鄰居放進堆疊
- 堆疊空了就結束
和 BFS 比較，程式幾乎一樣，只是佇列換成堆疊，而且改成「取出時才標記」：同一個節點可能被好幾個鄰居放進堆疊，取出時再檢查一次就好。
另外，堆疊是後進先出，最後放進去的鄰居會最先被取出。為了讓順序和遞迴版相同（編號小的鄰居先走），鄰居要反著放。
用堆疊的迭代 DFS
注意堆疊裡會出現重複的節點，例如 2 先被 0 放進去，後來又被 3 放進去。取出時用 visited 擋掉重複的那一筆。最後印出的順序和遞迴版完全相同：0 1 3 2 4 5 6。
BFS 與 DFS 的比較
同一張圖、同一個起點：
| BFS | DFS | |
|---|---|---|
| 資料結構 | 佇列（先進先出） | 堆疊或遞迴（後進先出） |
| 順序（本課的圖，從 0 開始） | 0 1 2 3 4 5 6 | 0 1 3 2 4 5 6 |
| 走法 | 一層一層往外 | 一路走到底再回頭 |
| 時間複雜度 | O(V + E) | O(V + E) |
| 找無權重最短路徑 | 可以 | 不行，先找到的路不一定最短 |
兩者的時間複雜度相同：每個節點拜訪一次、每條邊看一次（無向圖每條邊從兩端各看一次）。
DFS 找到的路不一定最短。以本課的圖為例，DFS 從 0 走到 4 的路徑是 0 → 1 → 3 → 2 → 4（4 條邊）， 但 BFS 告訴我們最短只要 2 條邊（0 → 2 → 4）。要最短路徑就用 BFS；要「走遍」或要知道「誰在誰底下」，DFS 比較好用。
想一想：DFS 的順序與限制
同一張圖，遞迴 DFS 改從節點 6 開始，拜訪順序是什麼？
adj = [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2, 5], [3, 4, 6], [5]]
一張圖是 10 萬個節點串成的一直線（0–1–2–…–99999）。在 Python 從 0 做遞迴 DFS，會發生什麼事？
要在沒有權重的圖裡找「從 A 到 B 最少經過幾條邊」，應該用哪一種？
有向圖裡的環：白、灰、黑
有向圖裡，如果從某個節點出發、沿著箭頭走，可以走回自己，就叫做有環（cycle）。 課程先修就不能有環：「A 要先修 B、B 要先修 A」的話，兩門課都修不了。
用 DFS 找環時，把每個節點標成三種顏色：
| 顏色 | 意思 |
|---|---|
| 白（0） | 還沒走過 |
| 灰（1） | 走進去了、還沒走完，也就是還在呼叫堆疊裡 |
| 黑（2） | 它底下能走的都走完了 |
DFS 走到 u，看到一條邊 u → v：
- v 是灰色：v 還在呼叫堆疊裡，代表我們是從 v 一路走下來到 u 的，現在又從 u 指回 v，找到環
- v 是黑色：v 早就走完了，從 v 出發不會走回目前這條路，不是環
- v 是白色：往下走
只用「拜訪過、沒拜訪過」兩種狀態是不夠的：碰到拜訪過的節點，無法分辨它是灰色（環）還是黑色（不是環）。 下面的範例就有一條指向黑色節點的邊（4 → 2），請注意程式沒有把它當成環。
三色 DFS 偵測環
看 color 陣列：走進一個節點就變成 1（灰），走完變成 2（黑）。2、3 先走完變黑；後來從 4 看到 2，2 是黑色，略過；最後從 5 看到 1，1 還是灰色（呼叫樹裡 has_cycle(1) 還沒結束），找到環 1 → 4 → 5 → 1。
拓撲排序：安排先修順序
系上的課有先修關係：要先修「程式設計」才能修「資料結構」，要先修「資料結構」和「離散數學」才能修「演算法」…… 把每門課當成節點，「u 是 v 的先修」畫成 u → v，就得到一張沒有環的有向圖（DAG，directed acyclic graph）。
拓撲排序（topological sort）就是把所有節點排成一列，使得每條邊 u → v 裡，u 都排在 v 前面。也就是一份「照著修就不會卡住」的修課順序。
最直覺的做法叫 Kahn 演算法（A. B. Kahn 在 1962 年發表）：
- 算出每個節點的入度（in-degree），也就是有幾條邊指向它：還有幾門先修課沒修
- 入度是 0 的節點沒有先修，全部放進佇列
- 從佇列取出 u，排進答案；u 指向的每個 v，入度減 1（v 少了一門先修）
- 某個 v 的入度變成 0，就表示它的先修都修完了，放進佇列
- 佇列空了就結束
每個節點進出佇列一次，每條邊讓入度減一次，所以是 O(V + E)。
Kahn 演算法：入度與佇列
節點上方的紅字是入度。一開始「程設」和「離散」的入度是 0，先放進佇列。每修完一門課，它指向的課入度減 1；「演算」要等「離散」和「資結」都修完，入度才會變成 0。節點編號：0 程式設計、1 離散數學、2 資料結構、3 演算法、4 作業系統、5 編譯器。
拓撲排序的幾個性質
順序不一定唯一。 本課的圖裡，「程式設計」和「離散數學」誰先都可以，「演算法」和「作業系統」也是。 Kahn 演算法排出的是其中一種；佇列換成優先佇列（每次取編號最小的），就能得到字典順序最小的那一種。
順便判斷有沒有環。 如果圖裡有環，環上的節點入度永遠不會降到 0，永遠進不了佇列。
所以演算法結束時，只要排出來的節點數少於 n，就表示有環，範例最後的 if 就是在檢查這件事。
也可以用 DFS 做。 對每個節點做 DFS，在節點走完（塗成黑色）的那一刻把它加進串列，最後把串列倒過來，就是一個拓撲順序。 理由是：一個節點一定比它指向的所有節點晚走完，倒過來就變成排在它們前面。
| 方法 | 做法 | 判斷有環 |
|---|---|---|
| Kahn 演算法 | 入度 + 佇列 | 排出的節點少於 n |
| DFS | 走完的順序倒過來 | 走到灰色節點 |
兩種都是 O(V + E)。
想一想：環與拓撲排序
三色 DFS 走到 u，看到一條邊 u → v，而 v 是黑色。這代表什麼？
用 Kahn 演算法（佇列）排下面這張圖，會印出什麼？
adj = [[1, 2], [3], [3], []] # 0→1、0→2、1→3、2→3
對一張有環的有向圖執行 Kahn 演算法，會發生什麼事？
實作：最少要幾個學期
同樣的六門課，假設每學期可以修任意多門，只要先修課在之前的學期修完。term[v] 是 v 最早能在第幾學期修。請在 Kahn 演算法的內層迴圈補上一行：v 至少要排在 u 的下一個學期。想一想為什麼要用 max：「演算法」有兩門先修課，要等比較晚修完的那一門。
重點整理
- DFS 一路走到底再回頭；遞迴版最短，呼叫樹就是 DFS 樹
- 遞迴太深會用完呼叫堆疊，可以改用自己的堆疊；鄰居反著放，順序就和遞迴版相同
- BFS 與 DFS 都是 O(V + E)；無權重最短路徑用 BFS，DFS 找到的路不一定最短
- 有向圖找環用白灰黑三色：指向灰色節點（還在呼叫堆疊裡）才是環，指向黑色節點不是
- 拓撲排序把 DAG 排成「每條邊都從前指向後」的順序；Kahn 演算法用入度與佇列，排出的節點少於 n 就表示有環
- 拓撲順序不一定唯一
下一課：邊有了權重（距離、時間、票價），BFS 數「邊數」就不夠了。Dijkstra 演算法用優先佇列找出權重總和最小的路徑。