为什么 BFS 能在无权图中求出单源最短路径？

层序扩展为何保证最短

BFS 从源点开始，将其所有邻接点入队并记录距离为 1。处理完源点后，再从队列取出最早入队的节点，扩展它的未被访问的邻接点，距离设为当前节点距离加 1。由于队列先进先出，距离为 d 的节点必然在距离为 d+1 的节点之前被处理，形成逐层扩展。每个节点一旦被访问就立即标记，不再可能被更远路径更新。假设存在一条更短的路径，那么它的最后一条边必然来自某个已访问的下一层节点，这与按层扩展矛盾。因此首次访问时距离就是最短边数。

该机制可形式化为：访问节点 v 时，它的距离 d[v] 已是最短。若存在另一条路径到 v 的边数更少，则那条路径上必有一个节点 w 先被访问但尚未扩展，导致矛盾。实际上，BFS 访问节点的顺序就是按距离非递减排列的。这种性质使得 BFS 不需要像 Dijkstra 那样比较距离，只需一次访问即可确定结果，时间复杂度 O(V+E)。

社交网络最少转发次数

假设一个社交网络有 10 万个用户，用户间关注关系构成有向无权图，需要计算从某大 V 到另一用户的至少需要多少次转发才能触达。输入为邻接表，边数约 30 万。从大 V 节点执行 BFS，同时记录每个用户的前驱。当目标节点被首次访问时，立即得到最短转发次数，并通过前驱链回溯路径，如 A→B→C。整个过程在线性时间 O(V+E) 内完成，且没有 Dijkstra 优先队列的额外开销。

若改用朴素 DFS 找最短路径，可能先深入一条长链，需要遍历所有可能路径才能确认最短，最坏指数级。BFS 因为按层扩展，第一个到达目标节点的路径必然最短，无需搜索全部。此场景还要求记录具体转发路径，前驱数组正好满足，若只求距离则一个整数数组即可。

function bfsShortestPath(adj, s, t) {
  const n = adj.length;
  const dist = new Array(n).fill(-1);
  const prev = new Array(n).fill(-1);
  const q = [s];
  let head = 0;
  dist[s] = 0;
  while (head < q.length) {
    const v = q[head++];
    if (v === t) break;
    for (const u of adj[v]) {
      if (dist[u] === -1) {
        dist[u] = dist[v] + 1;
        prev[u] = v;
        q.push(u);
      }
    }
  }
  if (dist[t] === -1) return { dist: -1, path: [] };
  const path = [];
  for (let cur = t; cur !== -1; cur = prev[cur]) path.push(cur);
  return { dist: dist[t], path: path.reverse() };
}

// 测试：0-1-2-3, 0-4-3
const adj = [[1,4],[0,2],[1,3],[2,4],[0,3]];
console.log(JSON.stringify(bfsShortestPath(adj,0,3)));
// 孤立点
const adj2 = [[],[],[]];
console.log(JSON.stringify(bfsShortestPath(adj2,0,1)));
// 自环和重边
const adj3 = [[1,1],[0,0]];
console.log(JSON.stringify(bfsShortestPath(adj3,0,1)));

{"dist":2,"path":[0,4,3]}
{"dist":-1,"path":[]}
{"dist":1,"path":[0,1]}

BFS 最短路的适用边界

BFS 只在所有边权重相等（通常为 1）时有效。若边权不同，层序扩展不再对应路径长度累加，首次访问未必最短。例如一条直接边权 5 先访问，后到达的间接路径边权和反而可能更小。此时必须使用 Dijkstra 或 0-1 BFS（若权值为 0 和 1）等考虑实际权重的算法。若目标不可达，BFS 会遍历完所有可达节点后结束；队列仍会处理所有可达节点。

对于无权图，BFS 时间复杂度为 O(V+E)，空间 O(V)。若图特别大且需要多源点，可初始化多个源点入队，但需注意正确设置初始距离和访问标记。若存在负权边，BFS 完全失效，因为路径长度可能因负边而递减，不能用层序思想。此时应改用 Bellman-Ford 或 SPFA。

容易答错的地方

认为 BFS 只能用于无向图

BFS 对无向图和有向图都适用，只要边权为 1。有向图中 BFS 从源点沿出边扩展同样得到最短路径，只是不可达范围不同。

误以为需要松弛操作

无权图中首次访问即最短，无需比较距离更新。可结合边权为 1 的性质，每个节点只入队一次，避免重复处理。

面试官还会怎么问？

把知识连起来