DFS 与 BFS：递归、队列与图遍历详解

图遍历是算法学习的根基，而深度优先搜索（DFS）和广度优先搜索（BFS）作为最核心的两种遍历方式，掌握它们的原理能帮助你轻松攻克诸多复杂题目。接下来，我们从核心思想、代码实现到经典例题，逐步拆解这两个重要算法。

DFS：深入到底再回溯

DFS 全称为 Depth-First Search，中文常称为深度优先搜索。其核心策略是：沿着一条路径不断深入，直到无法继续，再返回上一步探索其他分支。

课程中展示了一个简洁的树结构：

AB CD

如果按先序遍历执行，DFS 的访问顺序为：A → B → D → C。

为什么会得到这个顺序？因为 DFS 优先走向更深层：

1. 从根节点 A 出发；
2. 先访问左子节点 B；
3. 从 B 继续向下，访问子节点 D；
4. D 没有子节点，回溯到 B，B 也没有其他子节点，再回溯到 A；
5. 最后访问 A 的右子节点 C。

递归实现

DFS 最自然的实现方式是递归，因为“继续深入”和“回溯”恰好对应函数调用栈的压入与弹出。

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [{ value: 'D', children: [] }]
    },
    {
      value: 'C',
      children: []
    }
  ]
};

function dfs(node) {
  if (!node) return;
  // 1. 先访问当前节点（先序遍历）
  console.log(node.value);
  // 2. 对每个子节点递归执行 DFS
  for (const child of node.children) {
    dfs(child);
  }
}

dfs(tree); // 输出：A B D C

递归调用栈自动实现了“回溯”：当 dfs(D) 执行完毕，程序会回到 dfs(B) 的循环中，继续检查 B 是否还有未遍历的子节点。

BFS：逐层向外扩散

BFS 全称为 Breadth-First Search，中文即广度优先搜索。其策略与 DFS 恰好相反：

用同一棵树做层序遍历，访问顺序是：A → B → C → D。

队列实现

BFS 通常借助队列实现。队列的“先进先出”特性确保我们按层次依次处理节点：

function bfs(root) {
  if (!root) return;
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift(); // 取出队首
    console.log(node.value); // 访问当前节点
    // 将子节点加入队尾
    for (const child of node.children) {
      queue.push(child);
    }
  }
}

bfs(tree); // 输出：A B C D

执行流程如下：

1. 初始队列：[A]；
2. 取出 A，输出 A，将 B、C 入队：[B, C]；
3. 取出 B，输出 B，将 D 入队：[C, D]；
4. 取出 C，输出 C，无子节点：[D]；
5. 取出 D，输出 D，遍历结束。

DFS 与 BFS 的对比

重点强调一个直觉：DFS 擅长“找路径”，BFS 擅长“找最短”。因为 BFS 第一次到达某个节点时，经过的步数一定是最小的。

DFS 的另一种写法：显式栈

通常用递归实现 DFS，但递归存在栈溢出风险（当树深度极大时）。实际面试和工程中，DFS 也常用显式栈模拟递归过程：

function dfsWithStack(root) {
  if (!root) return;
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop(); // 取出栈顶
    console.log(node.value); // 访问当前节点
    // 注意：为了先访问左子节点，需将右子节点先入栈
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

dfsWithStack(tree); // 输出：A B D C

使用栈的好处是可控性更强，不会因递归过深导致调用栈溢出；缺点则是代码稍显繁琐。建议两种实现方式都熟练掌握。

经典题目练习

DFS 和 BFS 是 LeetCode 上最基础的高频算法之一。下面精选几道经典题目，覆盖树与图两种场景。

LC 104：二叉树的最大深度

思路：深度即层数，每个节点的深度 = max(左子树深度, 右子树深度) + 1。这体现了 DFS 的递归思想。

function maxDepth(root) {
  if (!root) return 0;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

LC 112：路径总和

思路：从根节点开始，每次减去当前节点的值，走到叶子节点时判断剩余值是否为 0。

function hasPathSum(root, targetSum) {
  if (!root) return false;
  // 叶子节点
  if (!root.left && !root.right) {
    return targetSum === root.val;
  }
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

LC 102：二叉树的层序遍历

思路：典型的 BFS 应用，按层处理节点，每层单独收集结果。

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(currentLevel);
  }
  return result;
}

LC 111：二叉树的最小深度

思路：寻找最短路径，BFS 第一次遇到叶子节点时返回当前层数即可。

function minDepth(root) {
  if (!root) return 0;
  const queue = [[root, 1]];
  while (queue.length > 0) {
    const [node, depth] = queue.shift();
    if (!node.left && !node.right) {
      return depth;
    }
    if (node.left) queue.push([node.left, depth + 1]);
    if (node.right) queue.push([node.right, depth + 1]);
  }
}

LC 200：岛屿数量

思路：这是网格场景中 DFS/BFS 的经典题目。遍历每个格子，遇到陆地就启动一次搜索，将相连的陆地全部标记为已访问，岛屿计数加 1。

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== '1') return;
    grid[r][c] = '2'; // 标记为已访问
    dfs(r - 1, c);
    dfs(r + 1, c);
    dfs(r, c - 1);
    dfs(r, c + 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c);
      }
    }
  }
  return count;
}

从本题可以看出，在网格问题中 DFS 就是“朝四个方向继续走，越界或遇水则回头”，与树中递归思想完全一致，不同之处在于邻居变成了上下左右四个方向。

DFS / BFS 通用模板

将上述题目抽象，可总结出两个常用模板：

DFS 模板（递归版）：

function dfs(node, visited) {
  if (!node || visited.has(node)) return;
  visited.add(node);
  // 处理当前节点
  for (const neighbor of node.neighbors) {
    dfs(neighbor, visited);
  }
}

BFS 模板：

function bfs(start) {
  const queue = [start];
  const visited = new Set([start]);
  while (queue.length > 0) {
    const node = queue.shift();
    // 处理当前节点
    for (const neighbor of node.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

在图结构中，务必使用 visited 集合记录已访问节点，否则可能陷入死循环。

列表转树：list2tree

list2tree 是实际开发中非常常见的需求。后端返回的往往是扁平数组，前端需要将其转换为树形结构，用于渲染菜单、组织架构、评论回复等场景。

一个典型的扁平列表示例如下：

const list = [
  { id: 1, name: 'A', parentId: null },
  { id: 2, name: 'B', parentId: 1 },
  { id: 3, name: 'C', parentId: 1 },
  { id: 4, name: 'D', parentId: 2 },
];

转为树结构：

function list2tree(list) {
  const map = new Map();
  const roots = [];

  // 第一步：用 map 记录每个节点
  for (const item of list) {
    map.set(item.id, { ...item, children: [] });
  }

  // 第二步：将每个节点挂到父节点下
  for (const item of list) {
    const node = map.get(item.id);
    if (item.parentId === null) {
      roots.push(node);
    } else {
      const parent = map.get(item.parentId);
      if (parent) {
        parent.children.push(node);
      }
    }
  }

  return roots;
}

console.log(JSON.stringify(list2tree(list), null, 2));

核心思路：

1. 使用 Map 建立 id 与节点的映射，实现 O(1) 查找；
2. 遍历列表，将每个节点挂载到对应的父节点下；
3. parentId === null 的节点即为根节点。

该算法的时间复杂度为 O(n)，远优于嵌套循环查找父节点的方式。

我对 DFS 和 BFS 的理解

DFS 和 BFS 并非两种孤立的算法，而是两种解决问题的“视角”。

• DFS 就像一个人在迷宫中不断探索，遇到死胡同就原路返回，适合穷举所有可能性；
• BFS 像一滴水落在湖面，波纹一圈一圈向外扩散，适合寻找最短、最近、最浅的目标。

list2tree 也让人意识到，算法知识与实际业务紧密相连。后端返回数组、前端需要树，中间的转换看似简单，但背后用到的哈希映射和递归思想，正是 DFS 和 BFS 这类基础算法的延伸。

后续刷 LeetCode 时，很多题目本质上都是这两种遍历思路的变形。先打牢这个基础，后面的回溯、动态规划、图论等内容都会轻松很多。