Breadth-First Search

Core Concepts

BFS (Breadth-First Search) — a traversal strategy that explores all nodes at distance d before any node at distance d+1; uses a FIFO queue. The first time BFS visits a node is via the shortest path in any unweighted graph — this is the central correctness invariant.

Level (layer) — the set of all nodes at the same hop-count from the source. The queue naturally groups them; processing one full level before starting the next is enforced by the inner-for-range idiom.

Frontier — the set of nodes currently being expanded; the boundary separating explored from unexplored regions.

Visited / seen set — tracks every node already enqueued to prevent duplicate queue entries. Must be updated at enqueue time, not dequeue time; marking at dequeue allows the same node to enter the queue multiple times before being processed.

Distance array / level map — maps each node to its BFS distance from the source; a side effect of traversal, not a separate pass.

Parent map — records the predecessor of each node at enqueue time; enables O(depth) path reconstruction by backtracking from target to source.

State-space graph — an implicit graph where nodes are problem states and edges are valid transitions; BFS finds the minimum number of transitions to reach a target state.

---

Internal Representation

The queue type and visited structure both affect constant factors significantly on large inputs.

---

Types / Variants

---

Key Algorithms

Shortest Path in Unweighted Graph

Finds minimum hop-count from source to all reachable nodes. The invariant: every node in the queue at iteration d is exactly distance d from source, because FIFO ensures earlier-enqueued (shorter) nodes are dequeued first. Time O(V+E), space O(V).

Level-Order Tree / Graph Traversal

Processes nodes grouped by depth. Use the inner-for-range pattern to separate levels:

while q:
    for _ in range(len(q)):
        node = q.popleft()
        # process node; enqueue children

Time O(n), space O(max width).

Multi-Source BFS

Pre-load all source nodes into the queue before the main loop; assign each distance 0. BFS then spreads from all sources simultaneously in lockstep — each node receives the distance to its geometrically nearest source. Time O(V+E), same as standard BFS.

Topological Sort — Kahn's Algorithm

Build an in-degree array. Enqueue all nodes with in-degree 0. On each dequeue, decrement every neighbor's in-degree; enqueue neighbors that reach 0. If total processed < V, the graph has a cycle and no valid topological ordering exists. Time O(V+E), space O(V).

Bipartite Check

Assign colors alternately during BFS (source → 0, neighbors → 1, their neighbors → 0, …). If any neighbor already has the same color as the current node, a same-color edge exists and the graph is not bipartite. Works on disconnected graphs by running per-component. Time O(V+E).

Connected Components

Run BFS from each unvisited node; each separate BFS identifies one component. Component count = number of BFS initiations needed. Time O(V+E).

Cycle Detection in Undirected Graph

Track the parent of each node at enqueue time. If a visited neighbor is not the recorded parent of the current node, a back edge (cycle) exists. Fails for multigraphs — see Edge Cases. Time O(V+E).

0-1 BFS

Replace the queue with a deque. When relaxing a weight-0 edge, push the neighbor to the front (appendleft); weight-1 edge, push to the back (append). This maintains the invariant that the deque front always holds the minimum-distance node — equivalent to Dijkstra but without a heap. Time O(V+E).

Bidirectional BFS

Maintain two BFS frontiers: one from source (dist_s), one from target (dist_t). After expanding one full level of the smaller frontier, check for intersection. When a node appears in both dist_s and dist_t, the shortest path is dist_s[node] + dist_t[node]. Must check all intersection candidates in the level — the first found is not necessarily minimum. Time O(b^(d/2)) where b = branching factor, d = shortest path length.

---

Advanced Techniques

BFS with State Compression

Solves: Problems where a "node" is a composite state — grid position plus held items, bitmask of visited required nodes, lock combination, etc. Mechanism: Encode the full problem state as a hashable object (tuple, integer bitmask, string). Use dist[(pos, mask)] or a dict as the visited/distance structure. BFS on this expanded state-space graph finds minimum-transition solutions. When to prefer over DFS + DP: Use BFS when there is no clear topological ordering of states and the problem asks for minimum steps. Prefer DP when transitions have a well-defined recurrence order (e.g., bitmask DP on TSP processes subsets in order of set size). Prefer DFS when you need all paths or optimal value rather than minimum count. Complexity: O(|state space| × branching factor); |state space| can be O(N × 2^K) for N positions and K required nodes.

BFS on Implicit / Layered Graphs

Solves: Word Ladder, sliding puzzle, lock combinations, string transformations — any problem where the graph is too large to materialize and neighbors are generated by a rule. Mechanism: Instead of an adjacency list, define a neighbors(state) generator that yields all valid successor states. BFS proceeds identically; the visited set is mandatory since there is no pre-built structure to bound revisitation. When to prefer over pre-building the graph: When the graph's edges are defined by a transformation rule and enumerating them in advance would cost more memory or time than generating on-the-fly. Prefer pre-building when the same graph is queried multiple times (offline). Complexity: O(branching factor × |reachable states|); branching factor for word ladder = 25 × word_length.

Virtual Source / Sink Augmentation

Solves: Multi-source problems where sources have different initial costs, or problems requiring simultaneous shortest-path from a set to all other nodes where pure multi-source BFS (distance = 0 for all sources) doesn't fit. Mechanism: Add a virtual node connected to each real source with an edge of weight equal to the source's initial cost. Run single-source BFS/Dijkstra from the virtual node. Every real node's distance absorbs the correct starting cost. When to prefer over multi-source BFS: Use when sources have unequal initial distances. Pure multi-source BFS assumes all sources start at distance 0; virtual source handles heterogeneous starting costs without modifying the main algorithm. Complexity: O(V+E) for BFS variant; O((V+E) log V) for Dijkstra variant.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Marking visited at dequeue instead of enqueue. The same unvisited node can be enqueued by multiple neighbors before any of them is processed. This produces duplicate entries and can corrupt distance values. Fix: add to visited (or dist) immediately before calling q.append.

• Using list.pop(0) as the queue. Python list removal from the front is O(n); on a graph with 10^5 nodes this silently degrades O(V+E) BFS to O(V²). Always use collections.deque with popleft().

• Single-source BFS on a disconnected graph. Nodes in other components are never visited; querying their distance returns a missing key or a sentinel infinity. Either initialize all distances to infinity upfront or explicitly handle "unreachable" in the return.

• Grid bounds unchecked before enqueue. Python negative indices silently wrap around; grid[-1][0] accesses the last row, not an out-of-bounds error. Always guard with 0 <= r < rows and 0 <= c < cols before enqueuing.

• Mutating a shared state object to generate neighbors. In implicit graph BFS, if you modify a single state object for each neighbor and enqueue the object reference, all queue entries point to the same (last) state. Generate a new state per neighbor.

• Cycle detection in multigraphs via parent tracking. The check neighbor != parent fails when two parallel edges connect the current node to its parent — the second parallel edge is a back edge but parent-tracking accepts it. For multigraphs, track the edge index rather than the parent node.

• Bidirectional BFS: checking mid-level instead of post-level. If you terminate as soon as any node appears in both frontiers, you may return a non-minimum answer when a shorter meeting path is completed later in the same level. Finish expanding the full current level of the smaller frontier before evaluating all candidates.

• 0-1 BFS with a regular queue. Treating weight-0 and weight-1 edges identically breaks the distance ordering guarantee; the result is not necessarily shortest. Use deque with appendleft/append discrimination.

• Bitmask overflow in state-space BFS. States encoded as 1 << i for i up to 30 fit in a 32-bit int; beyond that, Python handles arbitrary precision automatically, but C++/Java require long. In Python this is not a runtime error, but a state space of 2^30+ items will MLE.

• Source equals target edge case. Code that only checks the target at dequeue will still return 0 correctly if it pre-initializes dist[src] = 0 before the loop, but code that initializes inside the loop may return 1. Check if src == target: return 0 before starting.

---

Implementation Notes

• from collections import deque — the only correct queue for BFS in Python; list.pop(0) is O(n).
• Define direction arrays once at the top of the function: dirs = [(0,1),(0,-1),(1,0),(-1,0)] for 4-directional grids; avoids rewriting four cases per problem and is easy to extend to 8-directional.
• BFS is inherently iterative; Python's default recursion limit of 1000 is irrelevant to BFS correctness.
• defaultdict(list) for adjacency silently creates empty entries on read — use adj.get(node, []) if the graph object must stay unmodified during traversal.
• When returning level count (tree depth, minimum distance), the outer while-loop iteration count equals the number of levels processed; increment a depth counter once per outer loop, not per node.
• For Kahn's topological sort, computing in-degrees requires one full pass over all edges before the BFS begins; don't compute them lazily inside the loop.
• In 0-1 BFS, the deque replaces both the queue and the priority queue — importing heapq is unnecessary and would add log overhead.

---

Cross-Topic Relations

See graph.md for graph representation, DFS, and directed-graph algorithms. See dynamic-programming.md for DP on DAGs and bitmask DP.

---

Interview Reference

Must-Know Problems

Shortest Path / Grid BFS

• Number of Islands (LC 200) — component counting baseline
• Rotting Oranges (LC 994) — multi-source BFS; return -1 if unreachable
• 01 Matrix (LC 542) — multi-source from all zeros simultaneously
• Walls and Gates (LC 286) — multi-source distance fill
• Shortest Path in Binary Matrix (LC 1091) — 8-directional grid
• Minimum Knight Moves (LC 1197) — BFS with coordinate pruning

Level-Order Tree Traversal

• Binary Tree Level Order Traversal (LC 102) — inner-for-range baseline
• Binary Tree Zigzag Level Order Traversal (LC 103) — direction flip per level
• Minimum Depth of Binary Tree (LC 111) — early termination at first leaf
• Populating Next Right Pointers (LC 116 / 117) — level-linking during BFS
• Maximum Width of Binary Tree (LC 662) — column index tracking

Implicit / State-Space BFS

• Word Ladder (LC 127) — implicit graph; neighbor generation is the key implementation challenge
• Open the Lock (LC 752) — 4-digit deque state; dead-end handling
• Sliding Puzzle (LC 773) — board-state as string; BFS on permutations
• Minimum Genetic Mutation (LC 433)

Topological Sort (Kahn's)

• Course Schedule (LC 207) — cycle detection via count check
• Course Schedule II (LC 210) — return ordering; handle cycle
• Alien Dictionary (LC 269) — build graph from adjacent word pairs
• Parallel Courses III (LC 2050) — earliest finish time = max over topological levels

Bipartite / Coloring

• Is Graph Bipartite? (LC 785)
• Possible Bipartition (LC 886)

Advanced / Hard

• Word Ladder II (LC 126) — all shortest paths; BFS for levels + DFS for path reconstruction
• Shortest Path Visiting All Nodes (LC 847) — bitmask state BFS; O(2^N × N²)
• Cut Off Trees for Golf Event (LC 675) — BFS inside BFS; sorted order
• Minimum Cost to Make at Least One Valid Path (LC 1368) — 0-1 BFS on grid
• Jump Game IV (LC 1345) — group same-value indices; BFS with adjacency pruning

Additional LeetCode Coverage

• N-ary Tree Level Order Traversal (LC 429)
• Maximum Depth of N-ary Tree (LC 559)
• Shortest Path to Get All Keys (LC 864)
• Snakes and Ladders (LC 909)
• Shortest Bridge (LC 934)
• Numbers With Same Consecutive Differences (LC 967)
• Jump Game III (LC 1306)
• Time Needed to Inform All Employees (LC 1376)
• Nearest Exit from Entrance in Maze (LC 1926)

Clarification Questions to Ask

• Is the graph directed or undirected? (affects cycle detection and topological sort applicability)
• Can there be self-loops or parallel edges?
• Is the graph guaranteed to be connected, or must isolated nodes be handled?
• For grid problems: are diagonal moves allowed (4- vs 8-directional)?
• Is "path length" the number of edges or the number of nodes visited?
• For word transformation: does the start word count toward the transformation sequence length?
• Is a path from source to target guaranteed, or should "impossible" (return -1) be handled?
• Are edge weights uniform, or do weights vary? (determines whether BFS or Dijkstra applies)

Common Interview Mistakes

• Marking nodes visited at dequeue instead of enqueue, causing TLE on dense graphs due to duplicate queue entries.
• Returning before completing a full level when the problem requires a count of complete levels (e.g., minimum depth requires processing the entire last level before comparing).
• Not handling the source-equals-target case, which should return 0 immediately before any BFS runs.
• Assuming the grid is fully connected and omitting the "no path found" return after the BFS loop.
• In Word Ladder, generating all 26-character-swap neighbors but forgetting to skip the word itself, causing an infinite loop or wrong distance.
• In Kahn's topological sort, not checking if len(result) < V for cycle detection — the BFS terminates normally but the result is silently incomplete.
• In bidirectional BFS, expanding one frontier by an entire BFS rather than one level per iteration, losing the branching-factor reduction.
• Using heapq for standard BFS — adds unnecessary O(log n) overhead; BFS with a deque is strictly faster for unweighted graphs.

Typical Follow-Up Escalations

• "Return the actual path, not just its length." → Maintain a parent dict updated at enqueue; backtrack from target to source after BFS completes.
• "The graph has positive edge weights." → Switch to Dijkstra with a min-heap; BFS no longer guarantees shortest path.
• "Edge weights are 0 or 1." → Switch to 0-1 BFS with deque; O(V+E) without a heap.
• "Find all shortest paths, not just one." → Store all parents per node (not just one) at enqueue; reconstruct all paths via DFS/backtracking from target after BFS.
• "The graph is very large — can you do it faster?" → Bidirectional BFS; reduces O(b^d) to O(b^(d/2)) for known source-target pairs.
• "The graph changes dynamically as edges are added." → Union-Find for incremental connectivity; re-run BFS only on affected components for distance queries.
• "Find shortest path that visits all required nodes." → Bitmask DP + precomputed pairwise BFS distances; TSP variant for small required-node sets (≤ 20).