【算法图解】DFS：一条路走到黑

DFS（Depth-First Search，深度优先搜索）像走迷宫：

先沿着一条路走到底
走不通就回退（backtrack）
换一条路继续

DFS 是很多题的基础骨架：

图遍历
连通块/岛屿数量
路径搜索
拓扑排序（配合颜色标记）

1. DFS 的两种写法：递归与显式栈

1.1 递归 DFS（最直观）

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

  function visit(node) {
    visited.add(node)
    order.push(node)

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) visit(next)
    }
  }

  visit(start)
  return order
}

优点：代码短、表达清晰。

风险：递归深度过大可能爆栈。

1.2 显式栈 DFS（更工程）

function dfsIter(graph, start) {
  const visited = new Set([start])
  const stack = [start]
  const order = []

  while (stack.length) {
    const node = stack.pop()
    order.push(node)

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

  return order
}