sko.kr

广度优先搜索（BFS）

algorithmsgraph-traversaltree-traversalbfsqueueshortest-path
By sko•10/7/2025•7 min read

何时使用广度优先搜索

当你需要逐层探索节点或在无权图中找到最短路径时使用BFS。虽然最常用于层序遍历，但它也可以适用于：

  • 层序树遍历（经典用例）
  • 无权图中的最短路径（由于逐层探索保证最优）
  • 查找距离起点为k的所有节点
  • 检查图是否为二分图（可以将节点分成两组，其中同组内没有两个节点相连 - 通过在交替层中为节点着色完成）
  • 网页爬虫（在深入之前探索相同深度的链接）
  • 社交网络分析（查找n度分离内的连接）
  • 任何需要在移动更远之前探索当前"距离"的所有可能性的问题

示例问题

公司组织架构图：给定一个表示为树的公司层次结构，按层次打印所有员工以了解汇报结构。

        CEO
       /   \
     CTO   CFO
    /  \     \
  Dev1 Dev2  Acc1

Level 0: CEO
Level 1: CTO, CFO
Level 2: Dev1, Dev2, Acc1

这清楚地显示了管理层 - 首先是CEO的所有直接下属，然后是他们的所有直接下属，依此类推。

最重要的洞察

BFS在任何距离d+1的节点之前探索距离d的所有节点 - 通过使用队列（FIFO），我们保证节点按照它们被发现的确切顺序处理，这自动提供了逐层探索和无权图中的最短路径。

心智笔记：算法的天才之处在于队列的FIFO特性。当你发现一个节点的邻居时，它们进入队列的后面。这意味着当前层的所有节点在下一层的任何节点之前被处理。就像逐排填满剧院一样 - 你不能在第2排完全满之前开始第3排。

决策框架

在每个节点，你面临一个简单的决策：

  • 处理当前节点（标记为已访问）
  • 将所有未访问的邻居添加到队列中以供将来探索

队列强制执行顺序 - 你不决定何时处理节点，FIFO结构为你做这件事。

代码

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function bfs(root) {
  // 处理空树
  if (root == null) {
    return;
  }

  // 使用根节点初始化队列
  const queue = [root];
  let level = 0;

  // 逐层处理节点
  while (queue.length > 0) {
    // 捕获当前层的大小 - 这是关键！
    const levelSize = queue.length;
    const currentLevelNodes = [];

    // 处理当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      // 决策框架：处理当前节点
      const currentNode = queue.shift();
      currentLevelNodes.push(currentNode.val);

      // 决策框架：将未访问的邻居（子节点）添加到队列
      if (currentNode.left != null) {
        queue.push(currentNode.left);
      }
      if (currentNode.right != null) {
        queue.push(currentNode.right);
      }
    }

    // 输出当前层
    console.log(`Level ${level}: ${currentLevelNodes.join(", ")}`);
    level++;
  }
}

// 使用公司组织架构图的示例
const ceo = new TreeNode("CEO");
const cto = new TreeNode("CTO");
const cfo = new TreeNode("CFO");
const dev1 = new TreeNode("Dev1");
const dev2 = new TreeNode("Dev2");
const acc1 = new TreeNode("Acc1");

ceo.left = cto;
ceo.right = cfo;
cto.left = dev1;
cto.right = dev2;
cfo.right = acc1;

bfs(ceo);
// 输出：
// Level 0: CEO
// Level 1: CTO, CFO
// Level 2: Dev1, Dev2, Acc1

疑虑消除

常见疑虑："为什么我不能只使用DFS（深度优先搜索）来遍历树？反正最终会访问所有节点吗？什么使BFS对层序遍历特别？"

这是一个自然的问题，因为BFS和DFS都访问所有节点。让我们看看为什么BFS对某些问题至关重要。

为什么你可能认为DFS可以工作

考虑我们的公司组织架构图。使用DFS，你可能会想：

  • "我会先深入：CEO → CTO → Dev1，然后回溯"
  • "最终我会访问所有节点，所以有什么区别？"
  • "我不能只是跟踪深度并按级别分组节点吗？"

为什么这种想法错过了关键点

关键认识：BFS不仅仅访问所有节点 - 它以特定顺序访问它们，提供独特的保证！

让我们比较BFS与DFS的遍历顺序：

BFS顺序：CEO → CTO → CFO → Dev1 → Dev2 → Acc1
（第0层的所有节点，然后第1层的所有节点，然后第2层的所有节点）

DFS顺序：CEO → CTO → Dev1 → Dev2 → CFO → Acc1
（先深入，在层之间跳跃）

具体例子：查找最短路径

想象在无权图中从CEO到Acc1查找最短路径：

使用BFS：

步骤1：处理CEO（距离0）
步骤2：处理CTO、CFO（距离1） - 找到CFO！
步骤3：处理CFO的子节点 - 在距离2找到Acc1！

使用DFS（可能走更长的路径）：

步骤1：处理CEO
步骤2：处理CTO（向左走）
步骤3：处理Dev1（向左更深）
步骤4：回溯到CTO
步骤5：处理Dev2
步骤6：一直回溯到CEO
步骤7：最后处理CFO
步骤8：处理Acc1

DFS可能会找到一个节点，但不能保证是通过最短路径！

为什么队列是必不可少的

BFS中的队列就像一个"代际跟踪器"：

  1. 第0代（根）：队列中只有CEO
  2. 第1代（子代）：CTO和CFO添加到队列
  3. 第2代（孙代）：Dev1、Dev2、Acc1添加到队列

FIFO属性确保：

  • 所有第1代节点在任何第2代节点之前处理
  • 这在DFS的栈（LIFO）或递归调用栈中是不可能的

层大小技巧

BFS中启用逐层处理的关键行：

const levelSize = queue.length; // 当前层大小的快照

这精确地捕获当前层有多少个节点。即使我们在处理时向队列添加新节点，我们也确切知道一层何时结束，下一层何时开始。

为什么这保证了正确性：

  • 当我们开始处理一层时，队列只包含该层的节点
  • 当我们处理每个节点时，我们将其子节点（下一层）添加到队列
  • 但我们只处理levelSize个节点，所以我们在当前层完成时准确停止
  • 队列现在只包含下一层的节点

这种优雅的机制是为什么BFS可以保证层序遍历和最短路径的原因，这是DFS由于其深度优先的性质根本无法提供的东西。

← Back to Blog