Breadth-First Search

Breadth-First Search

Imagine you're in a maze and you want to explore every room on your current floor before going upstairs. That's exactly how Breadth-First Search (BFS) works — it explores all neighbors at the current depth before moving deeper.

BFS uses a queue (FIFO) to keep track of vertices to visit. It's like a line at a store — first person in line gets served first. This gives BFS its level-by-level exploration pattern.

How BFS Works

Start at a vertex, mark it as visited, and add all its neighbors to the queue. Then, while the queue isn't empty, dequeue a vertex, process it, and add all its unvisited neighbors to the queue. Rinse and repeat!

The beauty of BFS is that it guarantees you find the shortest path in an unweighted graph. Why? Because it explores all vertices at distance 1, then all at distance 2, and so on.

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  visited.add(start);
  
  while (queue.length > 0) {
    const vertex = queue.shift();
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return visited;
}

Shortest Path in Unweighted Graph

Need to find the shortest path between two points in a maze or network? BFS is your best friend. Just track the distance from the start vertex as you explore, and when you reach the target, you've got your answer.

This is how GPS navigation finds the quickest route in terms of stops (not distance). Each intersection is a vertex, and BFS explores one intersection away, then two away, and so on.

function shortestPath(graph, start, end) {
  const queue = [[start, 0]];
  const visited = new Set([start]);
  
  while (queue.length > 0) {
    const [vertex, dist] = queue.shift();
    if (vertex === end) return dist;
    
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;
}