广度优先搜索

问题从哪里来

假设每条边的代价都一样：都是一步。从 A 出发，哪些节点距离 0 步、1 步、2 步、3 步？

第一个朴素想法

可以沿着一条路一直深入，例如 A -> B -> D -> G，然后再回来看近处的选择。这样可能先到很远的节点，而近处节点还没检查。

它为什么会痛

如果发现顺序可以一直向深处走，它就不再保证按起点距离从近到远。小的有向对比例子只隔离一个差异：先进先出的队列保持层次，而像栈一样后进先出的策略可能先暴露更深节点。

核心发明

BFS 使用队列（queue）：已发现的节点按先进先出等待。B 发现 D 和 E 时，C 仍然排在它们前面，因为 C 更早被发现。

互动可视化

形式化版本

BFS 从源点 s 开始，发现尚未发现的邻居，记录 distance[neighbor] = distance[current] + 1，记录 parent[neighbor] = current，然后把邻居入队。

这一页用已发现（discovered）或已访问（visited）表示节点已经被找到并入队。已展开（expanded）表示节点已经出队并完成扫描。

实现草图

function bfs(start: string, graph: Record<string, string[]>) {
  const queue = [start];
  let head = 0;
  const visited = new Set([start]);
  const distance: Record<string, number> = { [start]: 0 };
  const parent: Record<string, string | undefined> = { [start]: undefined };

  while (head < queue.length) {
    const current = queue[head++];
    for (const neighbor of graph[current]) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      distance[neighbor] = distance[current] + 1;
      parent[neighbor] = current;
      queue.push(neighbor);
    }
  }

  return { distance, parent };
}

可视化里的”出队”对应 queue[head++]，而不是 queue.shift()，这样 TypeScript 草图仍保持线性队列行为。

正确性直觉

队列可以形成 [剩余第 k 层 | 新发现第 k+1 层] 这样的边界。关键是剩余的第 k 层节点始终排在第 k+1 层节点前面，所以更远的节点不会提前展开。

复杂度

使用邻接表时，BFS 每个节点发现一次，并在节点展开时扫描它的邻接行。总时间是 O(V + E)，队列、距离表、父节点表和 visited 集合使用 O(V) 空间。

常见混淆

节点一被发现就标记，可以避免重复入队。在这个追踪中，E 和 F 都会尝试 G，但 G 保留第一次发现时的父节点。

BFS 找到的是按边数计算的最短路径。如果边有不同代价，边数最少的路径不一定总代价最低。

距离是数字。父节点指针用来恢复实际路径树。

图谱连接

BFS 依赖图的基础：它会反复询问当前节点的直接邻居。Dijkstra 保留前沿和距离思想，但按总代价最小来选择下一个节点，而不是按队列顺序。

预测练习

1. 展开 B 之后，为什么 C 仍排在 D 和 E 前面？
2. 当 E 扫描 G 时，为什么 parent[G] 仍是 D？
3. 如果把队列换成栈，会发生什么？
4. 为什么带权三角形需要 Dijkstra，而不是 BFS？

图谱连接 : 广度优先搜索