运营要做一个「你们之间隔了几个人」的小功能,输入两个用户 id,返回最少经过几个中间人。同事写了一个深度优先搜索(DFS),找到一条能走通的路径就返回。测试环境里两个账号确实连通,结果看起来没问题。上线后有人截图投诉:明明都在同一个小群里,页面却显示隔了 5 个人。

原因很直接:DFS 找到的是「一条能走通的路径」,不是「边数最少的那条」。它一头扎进第一个分支,走到终点就收工,从不回头比较别的路是不是更短。两个人当然连通,但「连通」和「最近」是两件事。

这篇讲清 BFS 为什么能保证最短、队列和分层在其中做什么、为什么必须在入队时标记,再把边权只有 0 和 1 的 0-1 BFS 与网格图最短路讲完。所有代码都在本机 Node.js 24 上跑过,输出原样贴出来。

现场:DFS 找到了一条路,但不是最短的那条

先把好友关系建成无向图。7 个用户,边表示「互为好友」,每个人手里有一张邻居列表。注意 1 号有两个邻居 2 和 7,DFS 会先走列表里的第一个。

const social = {
  1: [2, 7],
  2: [1, 3],
  3: [2, 4],
  4: [3, 5],
  5: [4, 6],
  6: [5, 7],
  7: [1, 6]
};

同事的 DFS 用一个 seen 集合防止绕圈,用一个 path 数组记录当前走过的点,找到终点就把路径复制一份返回。

function dfsPath(graph, s, t, seen = new Set(), path = []) {
  seen.add(s);
  path.push(s);
  if (s === t) return path.slice();
  for (const v of graph[s]) {
    if (!seen.has(v)) {
      const r = dfsPath(graph, v, t, seen, path);
      if (r) return r;
    }
  }
  path.pop();
  return null;
}
console.log(dfsPath(social, 1, 6));

本机输出是 [1, 2, 3, 4, 5, 6],一共 5 条边。可是从 1 到 6 明明有一条更短的路:1 连 7,7 连 6,只要 2 条边。DFS 先走了 2 号分支,顺着 2 到 3 到 4 到 5 一路走到底,碰到 6 就停了,根本没有机会看 7 号那条路。

DFS 在事故图上的走法
从 1 出发,先走列表第一项 2
2 走到 3,3 走到 4
4 走到 5,5 走到 6
碰到终点就返回,路径 5 条边
真正的近路 1 到 7 到 6 没被检查

同一个图换成分层扩展,结果就不一样。从 1 出发,距离 1 的点是 2 和 7;距离 2 的点里有 3 和 6;6 在第二层就被发现了,不需要走到第五层。这就是这篇要讲的 BFS(广度优先搜索,breadth first search):先看完近的,再看远的。

队列、距离数组与入队标记

BFS 的核心容器是队列(queue),特点是先进先出:先放进去的点先被处理。它和栈正好相反,栈是后进先出,DFS 用的就是栈,所以它总往最新发现的分支里钻。

除了队列,还需要两样东西。一个是距离数组,记录起点到每个点目前知道的边数;另一个是访问标记,防止同一个点被反复处理。距离数组本身就能兼任访问标记:值是 undefined 就代表还没到过,有数字就代表已经定下来了。

队列存放「已经发现、还没扩展」的点。队首取出,队尾加入,保证按发现的先后顺序处理。
距离数组记录起点到每个点的边数。起点是 0,其余点第一次被写入时就是最终答案。
邻接表每个点的邻居列表。扩展一个点时,只遍历它自己的邻居,总工作量跟着边数走。

正确版本不长,关键是标记的时机:发现一个邻居,先算距离、先标记,再入队。不能等它出队时才标记。

function bfs(graph, s) {
  const dist = { [s]: 0 };
  const q = [s];
  const order = [];
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    order.push(u);
    for (const v of graph[u]) {
      if (dist[v] === undefined) {
        dist[v] = dist[u] + 1;
        q.push(v);
      }
    }
  }
  return { dist, order };
}
console.log(bfs({ 1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: [] }, 1));

本机输出:距离是 {"1":0,"2":1,"3":1,"4":2,"5":2,"6":3},访问顺序是 [1,2,3,4,5,6]。1 号是起点距离 0,2 和 3 是它的直接邻居距离 1,4 和 5 距离 2,6 距离 3。访问顺序恰好是按距离从小到大排的,这就是分层的直观样子。

这里用了一个 head 下标,而不是每次 q.shift()。JavaScript 数组的 shift 要把后面所有元素往前挪,单次是 O(n);用下标假装出队,单次是 O(1)。数据量大时这个差别很实在,队列里存 10 万个点,反复 shift 会白白多出大量搬移。

现在看标记时机的问题。下面这个版本等到出队才把点加进 seen,而且重复出队时直接跳过。逻辑上还能算出正确顺序,但队列里会塞进重复的点。

function bfsLate(graph, s) {
  const q = [s], seen = new Set(), order = [];
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    if (seen.has(u)) continue;   // 重复的点被跳过
    seen.add(u);
    order.push(u);
    for (const v of graph[u]) if (!seen.has(v)) q.push(v);
  }
  return { order, queueLen: q.length };
}

用一个「1 连 2、3、4,2、3、4 都连 5」的小图跑,出队标记版本的访问顺序是 [1,2,3,4,5],看起来对,但队列长度是 7,因为 5 被 2、3、4 各塞进去一次。把跳过那一行删掉,访问顺序会变成 [1,2,3,4,5,5,5],同一个点被处理了三遍。入队就标记的版本,队列长度是 5,每个点只出现一次。

起点必须在入队前就标记。如果只标记邻居、忘了给起点写距离或放进 seen,遇到自环或者双边,起点会被重新入队,距离可能被改坏,队列也会多出一份。

分层:为什么第一次到达就是最少边数

BFS 可以想成一层一层往外扩。第 0 层只有起点;第 1 层是起点的所有未访问邻居;第 2 层是第 1 层所有点的未访问邻居;依此类推。队列的先进先出保证了「第 k 层的点全部处理完,才会处理第 k+1 层的点」,因为第 k 层的点总是比第 k+1 层的点先入队。

为什么第一次给某个点写上距离,这个距离就是最短的?反证一下:如果存在一条更短的路,它经过的点数更少,那么这条路的上一个点所在的层数一定更小,会在更早的轮次被处理。可它被处理时,就会把这个点标记上,轮不到现在的层来发现。所以第一次写入时,不可能还有更短的路径没被发现。

这个论证依赖两个前提:每条边的代价都相同,而且队列按层有序。少一个都不行。边权不相等时,「层」就不再等于「距离」,普通 BFS 会把一条权重 5 的边和权重 1 的边都算成一步,答案自然错。这也解释了后面为什么需要 0-1 BFS 和 Dijkstra。

实际项目里通常还要把路径复原出来。在 BFS 里多记一个 parent 数组,谁第一次发现了这个点,谁就是它在 BFS 树上的父亲。从终点沿着父亲一路往回走,就是一条最短路径。

const g = { 1: [2, 3], 2: [4], 3: [4, 5], 4: [6], 5: [6], 6: [] };
const dist = { 1: 0 }, parent = {}, q = [1];
let head = 0;
while (head < q.length) {
  const u = q[head++];
  for (const v of g[u]) {
    if (dist[v] === undefined) {
      dist[v] = dist[u] + 1;
      parent[v] = u;
      q.push(v);
    }
  }
}
const path = [];
let x = 6;
while (x !== 1) { path.unshift(x); x = parent[x]; }
path.unshift(1);
console.log(path, path.length - 1);

本机输出是 [1,2,4,6] 3,路径有 3 条边,和距离数组里的 6: 3 对得上。注意这条路径不唯一,1 到 3 到 5 到 6 也是 3 条边;BFS 给出的是它先发现的那一条,具体是哪条取决于邻居列表的顺序。

BFS 的保证

无权图上,第一次到达就是最少边数。按层扩展,队列先进先出,复杂度 O(V+E)。代价是要存整个队列,最坏情况下队列里有大量同一层的点。

DFS 的保证

只保证「能走到」,不保证「走得最短」。它适合判连通、找环、拓扑排序、枚举所有路径,不适合回答「最少几步」。递归实现还有栈深度限制。

复杂度要按表示法说清楚。用邻接表,每个顶点入队一次,每条边被检查一次(无向图两次),总时间 O(V+E)。用邻接矩阵,每扩展一个点都要扫一整行,总时间 O(V²),在稀疏图上会慢很多。空间是 O(V),队列和距离数组都跟顶点数成正比。

0-1 BFS:边权只有 0 和 1 时用双端队列

有些图不是每条边都算一步。比如地铁图里,同一线路相邻两站不额外收费,换一条线路算一次换乘;或者某个操作既可以免费改名,也可以花一次机会重试。这类图的边权只有 0 和 1,普通 BFS 会把 0 权边也算成一步,结果偏大。

0-1 BFS 的做法是把普通队列换成双端队列(deque,两端都能进出)。扩展出一个邻居时,如果这条边权重是 0,就把它放到队首;如果权重是 1,就放到队尾。这样距离小的点总是排在前面,队列里的距离始终大致有序,取队首就相当于取当前最近的点。

本机的例子是一张 6 个站点的换乘图。字母是站点,边上标 0 或 1:0 表示同一线路内免费换乘,1 表示跨线路要付一次代价。

const transit = {
  A: { B: 0, C: 1 },
  B: { C: 0, D: 1 },
  C: { D: 1, E: 0 },
  D: { F: 0 },
  E: { F: 1 },
  F: {}
};
class Deque {
  constructor() { this.front = []; this.back = []; }
  pushFront(x) { this.front.push(x); }
  pushBack(x) { this.back.push(x); }
  popFront() {
    if (!this.front.length) {
      this.front = this.back.reverse();
      this.back = [];
    }
    return this.front.pop();
  }
  get size() {
    return this.front.length + this.back.length;
  }
}
function zeroOneBfs(g, s) {
  const dist = {}, dq = new Deque();
  for (const u in g) dist[u] = Infinity;
  dist[s] = 0;
  dq.pushBack(s);
  while (dq.size) {
    const u = dq.popFront();
    for (const v in g[u]) {
      const w = g[u][v];
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (w === 0) dq.pushFront(v);
        else dq.pushBack(v);
      }
    }
  }
  return dist;
}
console.log(zeroOneBfs(transit, 'A'));

本机输出是 {"A":0,"B":0,"C":0,"D":1,"E":0,"F":1}。A 到 C 这条边标价 1,但 A 先走 B(0),B 再到 C(0),两段免费路把 C 的距离压到 0。同样,E 通过 C 免费到达,F 通过 D 或 E 都只要 1。

作为对照,同一个图用普通 BFS,输出是 {"A":0,"B":1,"C":1,"D":2,"E":2,"F":3}。它把每条边都当成一步,C 被算成 1,E 被算成 2,F 被算成 3,全都偏大。这不是实现写错,而是普通 BFS 根本不认识权重。

0-1 BFS 里一个顶点可能被多次入队,因为后发现的 0 权路径可能比先发现的 1 权路径更短。判断时用 dist[u] + w 和当前 dist[v] 比较,变小才入队,就能保证最终距离正确。每个点重复入队的次数是常数级,总复杂度仍然是 O(V+E)。双端队列可以用两个数组模拟,也可以用语言自带的 deque,不要用普通数组的 unshift 硬顶,那会退化成 O(n)。

网格图:上下左右走的最短路

网格图是最常见的无权图:一个二维格子,每个格子是一个顶点,上下左右相邻的格子之间有一条边。障碍物相当于把顶点删掉。走一步的代价固定是 1,所以最短路就是最少步数,正好用 BFS。

下面这张 4 行 4 列的迷宫,S 是起点,E 是终点,# 是墙。BFS 把每个格子的距离存在一个同样大小的二维数组里,没访问过是 -1,墙也保持 -1。

const maze = [
  ['S', '.', '.', '.'],
  ['.', '#', '.', '#'],
  ['.', '.', '.', '.'],
  ['#', '#', '.', 'E']
];
function gridBfs(grid) {
  const R = grid.length, C = grid[0].length;
  let sr = 0, sc = 0;
  for (let i = 0; i < R; i++)
    for (let j = 0; j < C; j++)
      if (grid[i][j] === 'S') { sr = i; sc = j; }
  const dist = Array.from({ length: R }, () => new Array(C).fill(-1));
  dist[sr][sc] = 0;
  const q = [[sr, sc]];
  let head = 0;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (head < q.length) {
    const [r, c] = q[head++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
      if (grid[nr][nc] === '#' || dist[nr][nc] !== -1) continue;
      dist[nr][nc] = dist[r][c] + 1;
      q.push([nr, nc]);
    }
  }
  return dist;
}
console.log(gridBfs(maze));
console.log(gridBfs(maze)[3][3]);

本机输出是 [[0,1,2,3],[1,-1,3,-1],[2,3,4,5],[-1,-1,5,6]],终点 E 的距离是 6。按这个距离数组倒着走,6 的上面是 5,5 的左边是 4,一路可以还原出一条 6 步的路。墙的位置始终是 -1,既表示不能走,也表示没有距离。

这个模板有几个固定要点。方向数组只写四个方向,斜着走要另外加,但斜走算一步还是两步,取决于业务定义,不能想当然。边界检查要在取格子之前做,否则会读到 undefined。终点可以在出队时提前返回,但距离数组已经写对,提前返回只是省时间,不影响正确性。

多源最短路是同一套代码的小改动:把所有起点一开始就放进队列,距离都设成 0,然后正常扩展。这样一次 BFS 就能算出每个格子到最近起点的距离,不需要对每个起点各跑一遍。火灾逃生、最近加油站、地图上找最近的地铁站,都是这个模型。

现象、原因与第一步排查

BFS 写错时,症状往往不是报错,而是「结果看起来对,但偶尔偏大」。下面这些现象可以按表里的第一步快速定位。

现象真实原因第一步查什么
DFS 找到的路径比实际最短的长DFS 只保证可达,不比较路径长度是否把「找一条路」当成了「找最短路」
所有距离整体偏大 1起点没设成 0,或者起点没入队初始化时 dist[s] = 0 且 q = [s]
队列异常长,同一个点出现多次出队才标记,重复邻居被反复入队标记是否写在 push 之前
大数据量下 BFS 越来越慢用 shift 出队,每次都要搬移整个数组是否用 head 下标假装出队
带权图用 BFS 算出的距离全错普通 BFS 把每条边都当成权重 1边权是否只有 0 和 1,还是需要用 Dijkstra
0-1 BFS 的结果比正解大0 权边也被放到了队尾w === 0 时是否 pushFront
网格最短路绕了一大圈方向数组写错,或者边界、墙的判断漏了四个方向是否对称,墙是否在入队前排除
不连通的点距离是 undefined,参与计算后变成 NaN没有给不可达的点一个明确的哨兵值输出前是否把未访问统一成 -1 或 Infinity

最容易混淆的是第一行和第五行。第一行是把「连通」和「最短」当成同一件事,第二行是把「无权」和「带权」当成同一件事。判断方法很简单:先问这张图的边是不是代价相同,再问要的是可达还是最少步数。两个答案都指向 BFS,才可以用这一篇的模板。

边界与代价

BFS 的第一个边界是权重。它只适用于每条边代价相同的图。边权只有 0 和 1 时可以用 0-1 BFS,边权是任意非负数时要用 Dijkstra,有负权时要用 Bellman-Ford 那类算法。把带权图硬塞进普通 BFS,得到的数字没有意义,因为它数的是边数,不是代价。

第二个边界是内存。BFS 要存整个队列和整张距离表,空间 O(V)。网格图上 V 是行数乘列数,1000 乘 1000 就是 100 万个格子,距离数组用 32 位整数要 4MB,还算能接受;但如果队列里塞的是对象或者坐标数组,开销会翻好几倍。能用一维数组或 Int32Array 压平,就别用二维对象。

第三个边界是图的连通性。从单个起点出发,只能覆盖它所在的那个连通块,其他连通块的距离永远是「不可达」。业务上要判断整张图是否连通,得在外面再套一层循环,对每个还没访问的点各跑一次 BFS。每次 BFS 的总量加起来仍是 O(V+E),但别只跑一个起点就下结论。

第四个边界是路径本身。BFS 给出的是边数最少的路径,不是权重最小、也不是转弯最少、更不是最好看的那条。如果需要「最少转弯」或者「优先走大路」,那是在边上加了别的代价,得换成带状态的 BFS 或者 Dijkstra,不能指望在普通 BFS 里改两行就解决。

DFS 也有它的位置。判连通、找环、拓扑排序、枚举所有路径,DFS 写起来更短;网格上做连通块染色,DFS 和 BFS 都行。但递归 DFS 在大图上可能把调用栈撑爆,几万个点就能触发栈溢出,改成显式栈才稳。选 BFS 还是 DFS,先看你回答的是「最少几步」还是「能不能到」。

当天能做的练习

  1. 用本文的 7 人好友图,分别跑 DFS 和 BFS,打印 DFS 的路径与 BFS 的距离数组,数一数两条路各有多少条边,解释差在哪。
  2. 把 BFS 的标记从入队改到出队,用「1 连 2、3、4,2、3、4 都连 5」的图,分别打印访问顺序和队列长度,确认重复入队发生在哪一步。
  3. 自己构造一张 0 和 1 权重的图,先跑普通 BFS 再跑 0-1 BFS,把两份距离数组并排列出来,指出哪些点被高估、高估了多少。
  4. 把网格 BFS 改成支持 8 个方向,比较 4 方向和 8 方向下终点的距离,并说明斜着走算一步时,「距离」还是不是步数。
  5. 用 parent 数组还原一条最短路径,验证路径边数等于距离数组里的值;再测两个不连通的点,确认返回值是一个明确的哨兵而不是 undefined。
环境说明:本文所有代码和输出都用 Node.js 24 在本机实际运行,包括 BFS 的距离与访问顺序、DFS 的路径、0-1 BFS 的距离数组、网格图的距离矩阵。不同语言里队列、集合的实现不同,性能数字会变,但分层和标记时机的结论不变。

小结与下一篇

三句话收一下:BFS 用先进先出的队列按层扩展,第一次到达就是最少边数;标记要在入队时做,不能等出队,否则同一个点会被反复塞进队列;边权只有 0 和 1 时换成双端队列,0 权走队首、1 权走队尾。

下一篇进入 Dijkstra。0-1 BFS 能成立,是因为权重只有两种,队列天然能按距离排好;一旦边权是 2、5、10 这样的任意非负数,双端队列就排不出来了,需要换成优先队列,每次取当前距离最小的点,再对它做松弛。那一篇会把松弛、堆优化和「负权为什么不行」讲清楚。