Breadth-First Search

How BFS works

Two ingredients: a queue of nodes to visit, and a visited set to avoid revisiting.

1. Start: enqueue the source node and mark it visited.
2. Loop: dequeue a node. For each unvisited neighbor, mark it visited and enqueue it. Process the dequeued node (record distance, check goal, etc.).
3. Stop when the queue is empty (full search) or when the goal is dequeued (search-and-stop).

The queue's FIFO discipline is what gives BFS its level-by-level property. Anything enqueued at distance k is dequeued before anything enqueued at distance k+1, because k-distance nodes were enqueued first.

BFS vs DFS

	BFS	DFS
Order of exploration	Level by level (breadth)	Branch by branch (depth)
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Time	O(V + E)	O(V + E)
Space	O(V) — queue holds a level	O(depth) — stack holds a branch
Shortest path (unweighted)	Optimal — finds it for free	Not guaranteed
Memory on wide graphs	High (queue blows up)	Low (only one branch in memory)
Memory on deep graphs	Low (one level)	High (full depth in stack)
Common applications	Shortest paths, level-order, web crawl, social network "people you may know" (within k hops)	Cycle detection, topological sort, connected components, maze solving with backtracking

Choose BFS when shortest-path or level-by-level matters; choose DFS when memory is tight on shallow-but-wide graphs or when the algorithm naturally backtracks.

When to use BFS

• Shortest path on an unweighted graph. The first time you reach the target, you've reached it via the shortest path. No relaxation, no priority queue.
• Level-order tree traversal. "Print the tree level by level" — that's BFS with a queue.
• Web crawler / link checker. Start at a seed URL, fetch its links, fetch their links, etc. BFS naturally crawls in waves of increasing depth.
• Social network "friends within k hops." BFS k levels deep gives you everyone reachable in k hops or fewer.
• Puzzle-state search. Rubik's cube, sliding puzzles, word ladders. Each state is a node; each move is an edge. BFS finds the minimum-move solution.
• Finding connected components in an unweighted graph. Run BFS from any unvisited node; all nodes it visits are one component. Repeat from the next unvisited node.

Pseudo-code

function bfs(graph, start):
    visited = set([start])
    queue = [start]
    distance = { start: 0 }
    while queue.length > 0:
        node = queue.dequeue()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.enqueue(neighbor)
    return distance

JavaScript implementation

function bfs(graph, start) {
  const visited = new Set([start]);
  const distance = new Map([[start, 0]]);
  const parent  = new Map([[start, null]]);
  const queue = [start];
  let head = 0; // avoid O(n) shift() — use head pointer for amortized O(1) dequeue

  while (head < queue.length) {
    const node = queue[head++];
    for (const neighbor of (graph[node] || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distance.set(neighbor, distance.get(node) + 1);
        parent.set(neighbor, node);
        queue.push(neighbor);
      }
    }
  }
  return { distance, parent };
}

// Reconstruct shortest path using the parent map
function shortestPath(graph, start, target) {
  const { parent } = bfs(graph, start);
  if (!parent.has(target)) return null; // unreachable
  const path = [];
  for (let node = target; node !== null; node = parent.get(node)) path.unshift(node);
  return path;
}

Note the head pointer trick — calling queue.shift() in a loop is O(n²) total because each shift moves every remaining element. Use a head index or collections.deque in Python.

Python implementation

from collections import deque

def bfs(graph, start):
    visited = {start}
    distance = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                parent[neighbor] = node
                queue.append(neighbor)
    return distance, parent

Famous BFS problems

Word Ladder

Transform "hit" → "cog" by changing one letter at a time, where every intermediate word must be in a dictionary. Minimum number of transformations?

Each word is a node; an edge connects two words that differ by exactly one letter. BFS from the start word to the target word gives the minimum number of transformations. The graph is implicit — generate neighbors on demand by trying every single-letter substitution and checking the dictionary. Bidirectional BFS dramatically speeds this up for distant pairs.

0-1 BFS (edges weighted 0 or 1)

If edge weights are only 0 or 1, you don't need full Dijkstra — use a deque. Push 0-weight edges to the front, 1-weight edges to the back. The front of the deque is always the next-shortest node. Time complexity stays O(V + E).

Common bugs and edge cases

• Marking visited on dequeue instead of enqueue. If you mark a node visited only when it comes out of the queue, you might enqueue the same node multiple times before it's processed. Always mark when you enqueue.
• Using arr.shift() as dequeue. JavaScript arrays' shift() is O(n). Across n nodes, BFS becomes O(n²). Use a head index, an actual queue class, or a deque.
• Forgetting the visited set. Without it, cyclic graphs cause infinite loops. Always check before enqueueing.
• Storing entire paths in the queue. Storing the full path-so-far for every queued node uses O(V × depth) memory. Instead, store only the current node and reconstruct paths from a parent map at the end. Same answer, far less memory.
• Using BFS for weighted shortest path. BFS finds fewest hops, not shortest weighted distance. For non-uniform edge weights, use Dijkstra (or Bellman-Ford for negative weights).