带父节点回溯的图 BFS 最短路

功能说明

该示例用广度优先搜索在无权有向图中寻找起点到终点的最短路径。返回结果包含完整节点序列与边数距离；起点等于终点时返回单节点路径与零距离；遍历完仍不可达时返回 null。由于 BFS 按层扩展，第一次遇到终点时的路径必然边数最少，适合路由跳数、依赖层级、社交关系度数等场景。

关键代码

队列使用数组加 head 下标而不是 shift，避免每次出队移动整个数组造成平方复杂度。visited 在入队时立即标记，防止同一节点被多个父节点重复加入。parents 记录每个节点第一次被发现时的前驱，命中终点后从终点沿父链回溯到起点，再反转得到正向路径。起点或终点不在图的键集合中时抛 RangeError，帮助尽早发现拼写错误。

使用注意

该实现只处理无权图；边有权重时应改用 Dijkstra 或 Bellman-Ford。邻接表中出现但未作为键登记的邻居仍会被访问，只是没有后续出边，调用方若要求严格闭包可预先校验。路径长度是边数，不是节点数。队列与父映射的内存与可达节点数成正比，超大图应改用迭代式外部存储。返回的路径数组是新建的，可安全修改。

验证方式

构建含多条路径的图，断言返回最短的那条且距离正确；测试起点等于终点、终点不可达与孤立节点；交换边方向验证有向性；用多分支图检查父节点回溯没有环；传入不存在的起点或终点断言 RangeError；确认原始邻接 Map 未被修改。

代码示例

export interface BfsResult {
  path: string[];
  distance: number;
}

export function shortestPath(
  graph: ReadonlyMap<string, readonly string[]>,
  start: string,
  goal: string,
): BfsResult | null {
  if (!graph.has(start)) throw new RangeError("start node is missing: " + start);
  if (!graph.has(goal)) throw new RangeError("goal node is missing: " + goal);
  if (start === goal) return { path: [start], distance: 0 };

  const queue: string[] = [start];
  const parents = new Map<string, string>();
  const visited = new Set<string>([start]);

  for (let head = 0; head < queue.length; head += 1) {
    const node = queue[head];
    for (const neighbor of graph.get(node) ?? []) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      parents.set(neighbor, node);
      if (neighbor === goal) {
        const path = [goal];
        let current = goal;
        while (current !== start) {
          const parent = parents.get(current);
          if (parent === undefined) return null;
          path.push(parent);
          current = parent;
        }
        path.reverse();
        return { path, distance: path.length - 1 };
      }
      queue.push(neighbor);
    }
  }
  return null;
}