patternDSA/Breadth-First Search

Core Pattern → Pattern 08

Breadth-First Search

Explore level by level. The only algorithm that guarantees the shortest path in an unweighted graph. One queue, one visited set.

Frequency:★★★★★

·~35 min·Intermediate·2 problems

Prev Graphs

The Core Shock

DFS finds a path — BFS finds the shortest path

DFS Path

Any path

Goes deep first — may return a path 5× longer than shortest

Wrong answer

BFS Path

Shortest path

Processes all distance-k nodes before distance k+1

Guaranteed optimal

The insight: a queue enforces level order. All nodes at distance 1 are processed before any node at distance 2. The first time you reach the target, you have taken the fewest possible steps — BFS cannot overshoot. Use collections.deque for O(1) popleft.

Two BFS Flavors

BFS on graphs vs BFS on trees — same algorithm, different structure.

Graph BFS

Queue holds (node, distance) pairs. Visited set prevents revisits. First time target is dequeued, its distance is the answer.

Use when: Use when: 'shortest path', 'minimum steps', 'minimum hops', 'fewest transformations'.

Shortest Path in GraphWord Ladder01 MatrixOpen the LockMinimum Knight Moves

Level-Order Tree BFS

Queue holds tree nodes. Level separation tracked by snapshotting queue size at start of each level. Each snapshot = one level.

Use when: Use when: 'level order', 'level averages', 'right-side view', 'minimum depth', 'zigzag traversal'.

Level Order TraversalRight Side ViewLevel AveragesMin Depth of TreeZigzag Traversal

The 3-Step BFS Framework

Three decisions before writing a single loop.

Initialize Queue + Visited

Use collections.deque, not a list. Append start node AND mark it visited before the while loop. Never mark visited inside the while loop — creates race conditions.

from collections import deque
visited = {start}
queue = deque([(start, 0)])

Mark visited at enqueue time, not at dequeue time. If you mark at dequeue, the same node can be enqueued multiple times before being processed.

Process Level by Level

For graph BFS: popleft, check neighbors, enqueue unvisited. For tree level-order: snapshot len(queue), loop exactly that many times to process one full level.

while queue:
    node, dist = queue.popleft()
    for nb in graph[node]:
        if nb not in visited:
            visited.add(nb)
            queue.append((nb, dist+1))

popleft() is O(1) on deque, O(n) on list. Always use deque. list.pop(0) makes BFS O(V²) instead of O(V+E).

Return on First Reach

For shortest path: return distance the instant the target is dequeued (or when target is first enqueued as a neighbor). First reach = shortest distance. No need to continue.

for nb in graph[node]:
    if nb == target:
        return dist + 1  # first reach = shortest
    if nb not in visited:
        visited.add(nb)
        queue.append((nb, dist+1))

Return immediately when target is found — BFS is already done. No need to process the entire graph.

BFS vs DFS — Decision Guide

The most important graph algorithm decision you will make.

Use BFS When

"Shortest path" or "minimum steps"

"Minimum hops / transformations"

Level-order or level-by-level output

"Closest node satisfying condition"

Multiple simultaneous sources spreading

Unweighted graph shortest distance

"How many levels to reach target?"

Word ladder / state-space problems

Use DFS Instead When

"Find ALL paths" (backtracking needed)

Cycle detection in directed/undirected

Connected components (order irrelevant)

Topological sort (post-order DFS)

Flood fill — full component marking

Maze / puzzle solving with backtrack

Tree pre/in/post-order traversal

Space matters — DFS uses O(depth) stack

On this page