广度遍历与深度遍历（BFS / DFS）

更新: 7/4/2026 字数: 0 字 时长: 0 分钟

题目描述

给定一个用邻接表表示的图（可能有环、可能不连通），从指定起点出发访问所有可达节点，输出访问顺序。要求分别用两种经典策略实现：

• 广度优先遍历（BFS, Breadth-First Search）：像水波纹一样，从起点开始一圈一圈向外扩散，先访问离起点最近的节点。
• 深度优先遍历（DFS, Depth-First Search）：沿着一条路一直走到底，走不通了再回退到最近的岔路口换一条路。

以样例无向图（起点 0，邻接表 0:[1,2] 1:[0,3,4] 2:[0,5] 4:[1,5]）为例： BFS 访问序列为 [0, 1, 2, 3, 4, 5]；DFS 访问序列为 [0, 1, 3, 4, 5, 2]。

思路拆解

暴力直觉：只管“走”，容易死循环

最朴素的想法是：从起点开始，看到相邻节点就走过去，再看它的邻居……但图可能有环（比如 0-1-4-5-2-0），如果不做任何记录，就会在环里无限打转，同一个节点被反复访问。

暴力解法的致命问题

不记录“谁已经访问过”，遍历就无法终止。判重（visited 集合）是图遍历的第一要务，这也是图遍历与纯树遍历最大的区别——树没有环，天然不需要判重。

点击展开：没有判重的错误暴力递归

// ❌ 反例：图中有环时会无限递归 / 栈溢出
function badDFS(node, adj) {
  console.log(node)
  for (const nb of adj[node]) {
    badDFS(nb, adj) // 没有 visited，0→1→0→1... 死循环
  }
}

从判重到两种“待办容器”

加上 visited 后，真正的差异只剩一个问题：接下来先处理哪个待访问节点？ 我们需要一个“待办容器”存放已发现但还没处理的节点，而容器的取放规则决定了遍历形态：

• 用队列（Queue，先进先出 FIFO）：先发现的先处理 → 离起点近的先访问 → BFS。
• 用栈（Stack，后进先出 LIFO）：后发现的先处理 → 总是深入最新的分支 → DFS。

核心思路

BFS 和 DFS 的代码骨架几乎一模一样，唯一的本质区别就是待办容器是队列还是栈。理解了这一点，你就同时掌握了两种遍历。DFS 还能用递归天然实现——因为递归调用栈本身就是一个“栈”。

BFS 的关键细节：入队即标记

BFS 里要在节点入队的那一刻就标记为已访问，而不是出队时才标记。否则同一个节点可能被多个邻居同时入队，导致队列里出现重复、层次被打乱。

DFS 的两种写法

DFS 既可以用显式栈迭代，也可以用递归（隐式利用系统调用栈）。递归写法更简洁，但在极深的图上可能栈溢出；迭代写法更稳健。下面的动画演示的是迭代式 DFS，便于直观看到栈的变化。

下面的交互动画可在 BFS / DFS 之间自由切换，完整演示访问顺序、队列/栈的变化与已访问集合，可单步、自动播放与重置：

图遍历 · 广度优先(BFS) vs 深度优先(DFS)

样例无向图，起点 0。切换模式观察队列 / 栈如何决定访问顺序。

队列 queue（队头在左 · FIFO）

0

访问序列 order

尚未访问

BFS 从节点 0 出发：把起点入队并标记已访问。队列遵循「先进先出」，保证按「层」逐圈扩散。

步骤 0 / 13

完整代码

BFS（队列，迭代）

/**
 * 广度优先遍历
 * @param {Object} adj 邻接表，如 { 0:[1,2], 1:[0,3,4], ... }
 * @param {number} start 起点
 * @return {number[]} 访问顺序
 */
function bfs(adj, start) {
  const visited = new Set([start]) // 入队即标记
  const queue = [start]            // 待办容器：队列 FIFO
  const order = []

  while (queue.length) {
    const node = queue.shift()     // 队头出队
    order.push(node)
    for (const nb of adj[node]) {
      if (!visited.has(nb)) {
        visited.add(nb)            // 关键：入队时就标记
        queue.push(nb)             // 入队到队尾
      }
    }
  }
  return order
}

性能提示

Array.prototype.shift() 是 操作，数据量大时会让 BFS 退化到 。生产环境应改用双端队列或用一个下标指针模拟出队（let head = 0; queue[head++]），把出队降到 。

DFS（栈，迭代）

/**
 * 深度优先遍历（迭代式，用显式栈）
 * @param {Object} adj 邻接表
 * @param {number} start 起点
 * @return {number[]} 访问顺序
 */
function dfsIterative(adj, start) {
  const visited = new Set()
  const stack = [start]            // 待办容器：栈 LIFO
  const order = []

  while (stack.length) {
    const node = stack.pop()       // 栈顶出栈
    if (visited.has(node)) continue // 出栈时判重
    visited.add(node)
    order.push(node)
    // 逆序压栈，使较小编号邻居先被处理
    for (const nb of [...adj[node]].reverse()) {
      if (!visited.has(nb)) stack.push(nb)
    }
  }
  return order
}

DFS（递归，最简洁）

点击展开递归写法

function dfsRecursive(adj, start) {
  const visited = new Set()
  const order = []
  function dfs(node) {
    visited.add(node)   // 进入即标记
    order.push(node)
    for (const nb of adj[node]) {
      if (!visited.has(nb)) dfs(nb) // 递归深入
    }
  }
  dfs(start)
  return order
}

复杂度分析

设图有 个顶点、 条边（邻接表存储）。

遍历方式	时间复杂度	空间复杂度	待办容器	典型用途
BFS			队列 (FIFO)	无权图最短路径、按层扩散
DFS（迭代）			显式栈 (LIFO)	连通分量、拓扑排序、找环
DFS（递归）			系统调用栈	代码最简，但受递归深度限制

每个顶点入队/入栈一次、出一次；每条边在遍历邻居时被检查常数次，故时间为 。空间主要来自 visited 集合与待办容器，最坏 。

边界与易错点

易错点

1. 必须判重：图有环，缺少 visited 会死循环。这是与树遍历最大的不同。
2. BFS 入队即标记：应在入队时而非出队时加入 visited，否则同一节点会被重复入队，破坏层次性。
3. 不连通图：若要遍历所有节点，需对每个未访问节点都发起一次遍历（外层再套一个 for 循环遍历所有起点）。
4. shift() 的性能陷阱：JS 中数组 shift() 为 ，大图 BFS 请用下标指针或双端队列。
5. DFS 递归深度：链状或超大图上递归可能栈溢出，改用迭代式显式栈更安全。
6. 邻居遍历顺序：访问序列依赖邻接表中邻居的顺序；迭代式 DFS 若想与递归结果一致，压栈时需逆序压入。
7. BFS 最短路径的前提：BFS 求最短路仅在**无权图（每条边权相同）**下成立，带权图应改用 Dijkstra 等算法。

一句话总结

判重是前提，队列出层、栈入深：BFS = visited + 队列逐层扩散，DFS = visited + 栈（或递归）一路到底。骨架相同，容器不同。