本节我们学习两种关键的基本算法思想：DFS（深度优先搜索）和BFS（广度优先搜索）。这两种算法和栈、队列有着千丝万缕的关系，如果前两节你认真学习掌握了，那么这一节对你来说相信不是问题。

深度优先搜索思想：不撞南墙不回头的“迷宫游戏”

⚡ 30 秒速记

• DFS 沿一条分支走到底，走不通才回退；递归调用栈或显式栈都能实现。
• 图搜索必须在“入栈/进入递归”时标记 visited，否则有环图会重复访问甚至死循环。
• 时间复杂度是 O(V + E)；空间最坏 O(V)，树高为 h 时递归栈通常是 O(h)。
• DFS 擅长枚举路径、连通性、拓扑与回溯，不保证无权图最短路。

DFS 会沿当前分支一直向深处搜索，走不通时再回退到最近的岔路口。 它可以用递归调用栈实现，也可以自己维护显式栈，本质都是后进先出。遍历有环图时，我一般会在节点入栈或进入递归时标记 visited，避免重复访问甚至死循环。它适合路径枚举、连通性和回溯，时间为 O(V + E)，但不保证找到无权图的最短路径。

回答参考：“DFS 的核心不是递归语法，而是后进先出的待办集合。我会先定义访问标记时机，再说明当前路径与已完成节点各代表什么。”

function dfs(graph, start) {
  if (start == null) return []
  const stack = [start]
  const visited = new Set([start])
  const order = []

  while (stack.length) {
    const node = stack.pop()
    order.push(node)
    const neighbors = graph.get(node) ?? []
    for (let i = neighbors.length - 1; i >= 0; i -= 1) {
      const next = neighbors[i]
      if (!visited.has(next)) {
        visited.add(next)
        stack.push(next)
      }
    }
  }
  return order
}

💬 面试官追问

• 迷宫页面把 DFS 理解成“必须写递归”，代码改为数组 stack 后评审认为已经不是 DFS，你会怎样用执行现象反驳？

  只要待办节点按后进先出处理，搜索就会沿一条分支持续深入，遇到无路可走再回到最近分叉点，这仍是 DFS。递归只是借用函数调用栈实现同一调度方式；显式栈更便于控制深度，但邻居压栈顺序会直接影响访问顺序。

• 关系图中一个节点被多个前驱指向，页面内存突然上涨；代码直到 pop() 后才写入 visited，为什么会出现大量重复项？

  节点在真正弹出前仍被视为未访问，因此多个前驱都可能把它压入栈中，造成重复状态和更高的空间峰值。通常应在首次入栈时立即加入 visited，从源头阻止再次入栈；若业务需要枚举不同路径，节点级去重又可能过早剪枝，需改为路径状态。

• 路由依赖图可能出现环，开发只把当前节点放进 path，回退时删除，却没有全局 visited，查询为何可能反复绕圈？

  当前路径集合只能阻止本轮路径内的直接成环，节点退出路径后仍可能从其他分支再次进入。若目标是普通可达性遍历，应使用全局 visited 并在入栈时标记；若目标是枚举所有简单路径，则保留路径级标记，但必须接受重复探索和更高计算成本。

• 同一份邻接表，递归版访问顺序是 A、B、C，改成显式栈后却变成 A、C、B，你会检查哪段代码？

  应检查邻居压栈顺序，因为栈是后进先出，按邻接表正序压入会让最后一个邻居先被访问。若要复现递归中从左到右的顺序，应从邻接表末尾向前压栈；这只影响确定性的访问次序，不改变 DFS 的可达性结果。

• 导航页面既要找到出口，也要展示一条可回放路线；团队在“栈内容就是路径”和 parent 映射之间争论，你会选哪种？

  若显式栈中的元素始终代表当前分支，命中出口时栈内容可以直接形成路线，但常见的待办栈会同时保存尚未探索的分支，并不天然等于路径。通用实现更适合在首次发现节点时记录 parent，命中后反向恢复；代价是为已发现节点额外保存映射。