B

BigN Primer

Data Structures & Algorithms Guide

LearnFoundation

Breadth-First Search — Level Order Thinking

Learn how BFS explores graphs layer by layer, powers shortest unweighted paths, and pairs perfectly with queues.

BFSGraphsTraversal

Problem Statement

Master the breadth-first traversal pattern so you can discover the shortest number of edges between two nodes, detect connected components, and reason about level-order properties in trees and graphs.

Why This Problem Matters

  • Many graph interview prompts (word ladders, friend circles, closest meeting nodes) hinge on the “fewest edges” guarantee that BFS provides.
  • BFS shows up outside of graphs too: level order traversal in trees, shortest transformation sequences, and multi-source contagion simulations.
  • Queues and visited bookkeeping test whether you can manage auxiliary data structures cleanly under pressure.

Thought Process

Model neighbors explicitly

Decide on an adjacency list or implicit neighbor generator. Interviewers want to hear how O(V + E) work is achieved by visiting each edge once.

Track visited as soon as you enqueue

Marking nodes when they are enqueued, not dequeued, prevents duplicating work and keeps the queue bounded.

Capture layer semantics

Use queue length snapshots to separate levels or store distance alongside nodes if the problem needs exact step counts.

Step-by-Step Reasoning

  1. Initialise a queue with the starting node and mark it visited.
  2. While the queue is not empty, process the current layer size.
  3. Pop each node, perform the required action (collect, check goal, accumulate distance).
  4. Push every unvisited neighbor onto the queue and mark visited immediately.

Dry Run

Graph: A → {B, C}, B → {D}, C → {D}, D → {}

BFS order is A, B, C, D. Node D is reached in two edges, which is the fewest possible from A.

Grid shortest path with walls

Treat each cell as a node and neighbors as four directions. BFS ensures the first time you pop the target cell is the shortest number of steps.

Complexity Analysis

Time

O(V + E)

Space

O(V)

Why

Every vertex and edge is explored at most once; the queue and visited set store at most all vertices in dense layers.

Annotated Solution

JAVA
import java.util.*;

public class GraphTraversal {
  public static List<Integer> bfs(Map<Integer, List<Integer>> adjList, int start) {
    Queue<Integer> queue = new ArrayDeque<>();
    Set<Integer> visited = new HashSet<>();
    List<Integer> order = new ArrayList<>();

    queue.offer(start);
    visited.add(start);

    while (!queue.isEmpty()) {
      int node = queue.poll();
      order.add(node);

      for (int neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
        if (visited.add(neighbor)) {
          queue.offer(neighbor);
        }
      }
    }

    return order;
  }
}

Using a queue models the level-by-level expansion. Visiting neighbors as soon as they are queued keeps the runtime linear and prevents repeated nodes.

Common Pitfalls

  • Marking visited only when dequeued leads to duplicate enqueues and potential exponential blow-ups.
  • Forgetting to handle weighted edges—BFS only works for unit or uniform costs.
  • Mixing directed and undirected edges without normalising the adjacency list can miss reachable nodes.

Follow-Up Questions

  • Extend BFS to support multi-source problems by pushing all starting points initially.
  • Adapt BFS for binary maze problems where you also reconstruct the path by storing parents.
  • Combine BFS with bitmask visited states for puzzles that require tracking additional dimensions.

Key Takeaways

Queues and visited sets are inseparable partners for BFS on graphs.
Snapshotting queue length makes it easy to capture layer boundaries or compute distances.
BFS generalises to multi-source scenarios by seeding the queue with every starting node.
Back to Articles