题目重点：对比预计算全源 BFS/Floyd 与按查询 BFS，并解释十亿节点下必须先问图的表示。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码给定显式有向邻接表、节点编号 0..V−1，返回距离，不能到达返回 −1；无向图要添加反向边。
- 问题的重复查询版本按静态图讨论；如果边更新，预计算全距会失效。十亿节点仅作规模追问，题目未明确隐式邻居规则或真实边数，不能宣称任意图可在内存建完。
解题路线
- 因为边权全为 1，单源 BFS 按层首次到达就是最短边数；若只需一对点，可到目标时提前停止。
- V≈200 且 Q 很大时可对每个源运行 BFS 建 V×V 距离表，时间 O(V(V+E))、空间 O(V²)、单查 O(1)；密图上 Floyd-Warshall O(V³) 也简单，稀疏图全源 BFS 通常更划算。
- Q 小或 V 巨大时按查询 BFS，或把热点 source 的 BFS 行缓存；前提是能按需生成/读取邻居。十亿节点不能分配 V² 距离表，甚至完整显式邻接表也可能无法存放。
- 若追问路径而非距离，要保存 BFS parent 或预计算 next-hop；同距多路径的 tie-break 必须明示。
- 训练版在 169 张小型有向图上与独立 Floyd-Warshall 结果对照，覆盖不可达和环。
手动走一遍
200 个节点的全距表有 40,000 个距离单元，若有大量查询可接受。把 V 改成 10⁹ 后是 10¹⁸ 个单元，任何常规内存预算都不现实；此时先问图是否网格、地理路网或按规则生成，查询只访问局部还是必须遍历全图。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def bfs_distances(graph: list[list[int]], source: int) -> list[int]:
n = len(graph)
if source < 0 or source >= n:
raise ValueError("source outside graph")
distance = [-1] * n
distance[source] = 0
queue = deque([source])
while queue:
vertex = queue.popleft()
for neighbor in graph[vertex]:
if neighbor < 0 or neighbor >= n:
raise ValueError("edge endpoint outside graph")
if distance[neighbor] == -1:
distance[neighbor] = distance[vertex] + 1
queue.append(neighbor)
return distance
def all_pairs_bfs(graph: list[list[int]]) -> list[list[int]]:
return [bfs_distances(graph, source) for source in range(len(graph))]
复杂度
单源 BFS O(V+E) 时间、O(V) 辅助空间；全源 BFS O(V(V+E)) 时间与 O(V²) 距离空间；密图 Floyd O(V³) 时间、O(V²) 空间。隐式大图可按实际访问的 R 个点/E_R 条边估一次局部查询，但最坏仍可能遍历巨大图。
易错点与追问
容易失分的边界
- 边权全 1 仍用 Dijkstra 堆而未解释额外开销。
- 预计算后从 200 节点直接外推到 10⁹ 节点。
- 说 BFS 对任意十亿节点图都‘快’，忽略最坏遍历和图表示。
- 题目要求路径却只返回距离。
- 边修改后继续使用陈旧全距缓存。
继续深挖
- Q 多大时全源预计算比逐查询有利？
- 如果只有 100 个热点 source，怎样做按需缓存和失效？
- 路网带坐标时 A* 的启发函数必须满足什么条件？
- 若图跨机器存储，BFS 前沿通信会造成什么瓶颈？
