昨天我們終於把 Graph 從紙上的線條，變成程式真的能保存的資料。
例如一張簡化的路網：

我們可以用 Adjacency List 表示：

const graph = {
  A: ["B", "D"],
  B: ["A", "C", "E"],
  C: ["B"],
  D: ["A", "E"],
  E: ["B", "D"],
};

但把 Graph 存進程式，只解決了一半的問題。
接下來要探討的應用是：

我們要怎麼走過這張 Graph？

如果今天你被丟進一座迷宮

想像你站在迷宮入口。

眼前有兩條路：

入口
├─ 左邊
└─ 右邊

你可以有很多不同策略。
例如：

先看看左邊走一步
再看看右邊走一步
再回左邊走一步
...

也可以選擇另一種方式：

先挑一條路，一直走下去

比如先走左邊：

入口
→ 左邊
→ 再往前
→ 再往前
→ 死路

發現走不下去之後，再退回上一個岔路口：

死路
← 上一個位置
← 上一個岔路

然後改走另一條還沒試過的路。
這種：

先沿著一條路盡可能深入，走不下去再回頭

就是 Depth-First Search，通常簡稱 DFS。

Depth-First 到底是什麼？

名字其實已經把策略講完了。

Depth
→ 深度

First
→ 優先

這是一堂簡單的英文課，湊在一起就是：

先處理深度

假設現在有一張 Graph：

如果從 A 開始，而且我們先選擇 B，DFS 會這樣走：

A
↓
B
↓
D

D 已經沒有其他地方可以繼續走了，於是回到 B：

D
↑
B
↓
E

E 也走到底了，再回到 A：

B
↑
A

然後才走：

C
↓
F

整個順序可能是：

A → B → D → E → C → F

注意這裡最重要的並不是這一串順序本身。
因為 Neighbor 的排列方式不同，實際走訪的順序也可能不同。
真正重要的是它遵守的策略：

有路就繼續深入，沒路再回頭

這其實就是一種搜尋策略

假設你今天要在很多層資料夾裡找一個檔案：

Documents
├─ Work
│  ├─ Projects
│  │  ├─ frontend
│  │  │  └─ report.pdf
│  │  └─ backend
│  └─ Meetings
└─ Personal

我們可以先進 Work，再進 Projects，再進 frontend，一路往裡面走。
直到不能再深入，才退回去看其他目錄。
這跟迷宮其實是同一件事，表面上迷宮和資料夾看起來完全不同，但如果我們把它抽象成：

一個位置
→ 可以連到哪些其他位置？

它們都可以變成 Graph 或 Tree 的 traversal 問題。
而 DFS 做的事情就是：

決定我們探索這些關係時，要先往深處走

為什麼 DFS 會讓人想到 Stack？

還記得 Day 4 的 Stack 嗎？
Stack 的規則是 LIFO(Last In, First Out)。
也就是：

最後放進去的東西，最先拿出來

這其實非常符合 DFS 的需求。
假設我們現在在 A，發現可以走 B 和 C。
如果我們決定先探索 B，就要暫時記住：

C 之後還要回來處理

接著到了 B：

B
├─ D
└─ E

我們又選擇先走 D，此時程式其實一直在記：

之後還要回來處理哪些地方？

而 DFS 最自然的規則通常就是：

最近遇到、但還沒有探索完的路，最先繼續處理

這正好符合 Stack。
所以我們可以先建立一個很重要的關係：

Graph + Stack → DFS

用 Stack 看一次 DFS

還是這張圖：

從 A 開始：
以下都把陣列右側視為 Stack 的頂端

Stack:

[A]

拿出 A：

visit A

然後把它的 Neighbor 放進 Stack。
假設我們希望先探索 B，可能把 C、B 依序放進去：

[C, B]

Stack 最上面的 B 先被拿出來：

visit B

接著把 B 可以前往的地方放進去：

[C, E, D]

然後：

visit D

D 已經沒有其他地方可以前往，Stack 裡還剩下：

[C, E]

接著取出 E：

visit E

E 也沒有其他地方可以前往，Stack 裡還剩下：

[C]

接著取出 C：

visit C

把 C 可以前往的地方放進去：

[F]

最後取出 F：

visit F

你會發現 Stack 的 最後放進去 → 最先處理 自然而然產生了 DFS 的想法：

先往深處探索

一個簡化的 JavaScript DFS

如果真的用程式表達，可以寫成：

const dfsGraph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B"],
  F: ["C"],
};

function dfs(graph, start) {
  if (!graph[start]) {
    return;
  }

  const stack = [start];
  const visited = new Set();

  while (stack.length > 0) {
    const node = stack.pop();

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);
    console.log(node);

    const neighbors = graph[node] ?? [];

    for (let i = neighbors.length - 1; i >= 0; i--) {
      const neighbor = neighbors[i];

      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
}

dfs(dfsGraph, "A");

輸出順序會是：

A → B → D → E → C → F

因為 Stack 會先取出最後放入的項目，所以程式必須反向放入 Neighbor，才能優先探索排列在前面的 B 和 D。

這裡你不需要急著背程式碼。
只需要先看懂幾件事：

stack.pop()

代表：

拿最近放進去的 Node

而：

stack.push(neighbor)

則是在記錄：

這些地方之後還需要探索

所以整段程式真正做的事情仍然只是：

拿一個位置
→ 探索它
→ 把下一步放進 Stack
→ 繼續

可是為什麼需要 visited？

迷宮有一個很麻煩的地方，你可能繞一圈又回到原本的位置。
例如：

如果從 A 出發：

A → B → C → D → A → B → C ...

如果程式完全不知道：

這裡我來過了。

它就可能一直繞圈，所以 Graph traversal 通常需要記錄 visited。
例如：

const visited = new Set();

當我們第一次走到 A：

visited.add("A");

之後如果又看到 A：

if (visited.has("A")) {
  // 不需要再走一次
}

這其實是一個很重要的觀念：

Graph 不像 Tree，可能存在 cycle

Tree 往下走時，不會從 Child 突然又繞回祖先形成循環。
但在一般 Graph 完全可能，所以 DFS 通常不只需要 Stack，還需要知道哪些 Node 已經處理過。

這也呼應了前面 Tree 和 Graph 的差異

Day 6 談 Tree 時，我們看到：

root
→ child
→ child
→ leaf

那種結構會有一個方向感，但 Graph 不一定有這麼剛好的階層關係。

例如：

任何 Node 都可能和其他 Node 建立關係，甚至可以繞回去。
這也是為什麼到了 Graph 結構，visited 會開始變得非常重要。
因為我們不能再假設：

往下走就一定是在前往一個從沒去過的新地方

遞迴又是怎麼回事？

你可能也常看到 DFS 寫成遞迴 recursion：

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) {
    return;
  }

  visited.add(node);
  console.log(node);

  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

看起來 Stack 不見了，但 DFS 並沒有突然不需要 Stack。
只是這次我們沒有自己寫：

const stack = [];

而是利用 function call 本身的 call stack。
例如：

dfs(A)
  dfs(B)
    dfs(D)

當 dfs(D) 結束：

return

程式就會回到：

dfs(B)

接著繼續處理下一個鄰居。
這其實非常符合 一路深入 → 走到底 → 回到上一層 的行為。

所以你可以先建立這個理解：

DFS
├─ 可以自己使用 Stack
└─ 也可以利用遞迴的 call stack

兩種寫法不同，但背後的搜尋策略相同。

遞迴不是 DFS，Stack 也不是 DFS

很多大聰明會產生這種認知，看到遞迴就認為：

recursion = DFS

其實不是，Stack 也不是 DFS 本身。
真正的 DFS 是：

先深入，再回頭

Stack 只是非常適合實現這種策略的工具，遞迴則可以透過 call stack 自然表達它。
所以更精準地說：

搜尋策略：Depth-First

實作方式：
├─ explicit Stack
└─ recursion / call stack

資料結構是在支援我們選擇的策略。
這其實也回到了這個系列一直在談的事情：

我們不是先背資料結構，再硬找地方使用它

而是先決定：

問題需要什麼行為？

再選擇適合的表述方式與操作方式。

DFS 不等於「找到最佳路線」

還有一件事情現在就值得先分清楚。
DFS 可以幫我們探索 Graph，或是找出某個東西是否存在，但 DFS 本身並不代表找到的路徑就是最短路徑。
例如迷宮裡：

入口
├─ 左：繞很遠，但可以到出口
└─ 右：只要兩步就到出口

如果 DFS 一開始選擇左邊，它可能一路走了很久：

左
→ 左
→ 左
→ ...
→ 出口

然後找到答案了，它並不知道其實 右 → 出口更短。
因為 DFS 不關心哪條路最近？
它是選擇：

先把一條路探索到底

搜尋策略不同，會讓我們得到答案的方式也不同。

今天真正要記住的不是 DFS code

如果今天只記住：

stack.push(...)
stack.pop(...)
visited.add(...)

其實還沒有抓到 DFS 的核心，重要的是先理解：

當我們選擇「先沿著一條路深入到底」，我們其實已經選了一種搜尋策略

一旦選擇 Depth-First：

最近還沒探索完的路 → 優先繼續處理

Stack 就自然變成很適合的工具。
我們可以把今天濃縮成：

Graph + Stack + visited
↓
DFS

而遞迴只是另一種利用 call stack 實現相同策略的方法。

留給明天的問題

DFS 的做法是：

先選一條路
→ 一路走到底
→ 再回頭

但回到剛才的迷宮。
如果我們把問題從：

能不能找到出口？

轉向成：

哪一條路最少走幾步就能到出口？

那麼「一路深入到底」還是最合適的搜尋方式嗎？
明天我們來看另一種完全不同的策略：

先把離自己最近的地方都看完

也就是：

Breadth-First Search