中文
devexamples

Graph BFS Shortest Path With Parent Tracking

Breadth-first search over adjacency maps that reconstructs the shortest unweighted path and reports distance or null when unreachable.

TypescriptData Integrity

Code

snippet
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;
}

Related Examples