【算法图解】BFS：层层推进的搜索

BFS（Breadth-First Search，广度优先搜索）的感觉像“水波纹”：

从起点出发
先把距离为 1 的点都访问完
再访问距离为 2 的点
直到覆盖全图或找到目标

这使得 BFS 天然适合：

无权图的最短路径
树的层序遍历
最少步数/最少操作次数

1. BFS 的核心：队列

BFS 的数据结构是队列：

先入先出

这正好对应“按层扩散”。

2. 最小可运行模板（图）

图的表示方式很多，这里用邻接表：

const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['D'],
  D: [],
}

BFS：

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

  while (queue.length) {
    const node = queue.shift()
    order.push(node)

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

  return order
}

console.log(bfs(graph, 'A'))

（注意：shift() 在 JS 数组上是 $O(n)$，工程里更推荐用指针或双端队列。）

3. 为什么必须有 visited？

在图里如果没有 visited：

你会在环上无限循环

所以 BFS/DFS 在图中几乎总是需要 visited。

在树中通常不需要，因为树没有环。

4. BFS 求最短路径（无权图）

BFS 的关键性质：

第一次到达某个节点时，走过的边数是最少的

实现最短路径，你需要：

dist：距离（步数）
prev：前驱，用来还原路径

function shortestPath(graph, start, target) {
  const queue = [start]
  const visited = new Set([start])
  const prev = new Map()

  while (queue.length) {
    const node = queue.shift()
    if (node === target) break

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next)
        prev.set(next, node)
        queue.push(next)
      }
    }
  }

  if (!visited.has(target)) return null

  const path = []
  for (let cur = target; cur != null; cur = prev.get(cur)) {
    path.push(cur)
    if (cur === start) break
  }
  path.reverse()
  return path
}