BFS

BFS (Breadth-First Search)

Back to Index

Use when: shortest path in unweighted graph, level-order traversal, spreading problems (infection, walls).

Signal words: shortest path, minimum steps, level by level, nearest, word ladder.

Core Idea

Process nodes level by level using a queue. Guarantees shortest path in unweighted graphs.

Template

from collections import deque
 
def bfs(start):
    queue = deque([start])
    visited = {start}
    steps = 0
 
    while queue:
        for _ in range(len(queue)):  # process one level at a time
            node = queue.popleft()
            if node == target:
                return steps
            for neighbor in get_neighbors(node):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        steps += 1
    return -1  # not reachable

Key Questions to Ask

• Is this an unweighted shortest path problem? (BFS beats Dijkstra here)
• What counts as a “neighbor”? (adjacent cells, valid transformations, connected nodes)
• Do I need level tracking? (use the inner for loop over len(queue))

Multi-source BFS

Start with all sources in the queue simultaneously - useful for “nearest X to any Y” problems.

---

Problems Using This Pattern