中文
devexamples

Graph BFS Shortest Path Unweighted (JavaScript)

Find the shortest path in an unweighted graph using breadth first search with a predecessor map for path reconstruction.

JavascriptData Fetching

Code

snippet
function bfsShortestPath(graph, start, end) {
  if (start === end) return [start];
  const queue = [start];
  const visited = new Set([start]);
  const parent = new Map();
  while (queue.length) {
    const node = queue.shift();
    for (const neighbor of graph[node] || []) {
      if (visited.has(neighbor)) continue;
      visited.add(neighbor);
      parent.set(neighbor, node);
      if (neighbor === end) {
        const path = [end];
        let cur = end;
        while (parent.has(cur)) { cur = parent.get(cur); path.unshift(cur); }
        return path;
      }
      queue.push(neighbor);
    }
  }
  return null;
}

Related Examples