Graph AlgosAlgorithmaka level-order traversal, BFS

Breadth-First Search (BFS)

Explore a graph layer by layer from a source using a FIFO queue, visiting every node at distance d before any node at distance d + 1.

▶ VisualizePattern: Breadth-First SearchPractice (6)
Progress

Overview

BFS visits the nodes of a graph in order of their hop distance from a source: first the source, then all its neighbours, then all nodes two edges away, and so on. It is driven by a Queue: a node is dequeued, its unvisited neighbours are marked and enqueued, and the loop continues until the queue is empty.

Because it discovers nodes in non-decreasing distance order, BFS is the natural tool whenever "fewest steps" matters on an unweighted graph (see BFS Shortest Path (Unweighted)). It is also the traversal of choice for level-by-level processing such as Binary Tree level order, multi-source flood fills, and finding connected components without recursion.

traversalqueuelevel orderunweightedO(V + E)

Intuition

A mental model before the formal terms.

Drop a stone into still water: the ripple reaches every point at radius 1 before any point at radius 2. BFS is that ripple. The queue is the ring of the wavefront — everything in it is at distance d or d + 1, never further — and "visited" marks are the water already disturbed, so a ripple never re-enters the same spot.

How it works

  1. Mark the source visited and push it onto a queue.
  2. Pop the front node u. For every neighbour v of u that is not yet visited: mark v visited (at enqueue time, not at dequeue time), record parent[v] = u and dist[v] = dist[u] + 1, and push v.
  3. Repeat until the queue is empty. Nodes are popped in non-decreasing dist order; the order of first visits is the BFS order.
  4. For a disconnected graph, wrap the whole thing in a loop over all nodes and start a new BFS from each unvisited node.

Why it works

Invariant: at any moment the queue holds nodes of at most two consecutive distances d, d, …, d, d+1, …, d+1 in that order. Popping a distance-d node can only enqueue distance-(d+1) nodes at the back, so the invariant is preserved.

From the invariant, the first time a node is discovered it is reached via a node at minimal distance, hence its dist is the true shortest hop count. Marking at enqueue time guarantees each node enters the queue exactly once, so each edge is scanned at most twice (once per endpoint in an undirected graph): O(V + E) total.

Recognition

How to tell a problem wants this.

  • The problem says "shortest", "minimum number of moves/steps", "fewest edges" and every step costs the same.
  • You need level-by-level output: "nodes at depth k", "level order", "rotting spreads one minute at a time".
  • The state space is implicit (grid cells, word transformations, puzzle configurations) and you want the nearest goal state.
  • Multiple sources spread simultaneously — start with all of them in the queue at distance 0.
“minimum steps” → Breadth-First Search

Interactive visualization

Play, step, change the input. ← → and space work too.

A0BCDEFGHIJKL
Queue (front → back)
A
1/42Start BFS from A. Put it in the queue and mark it visited with distance 0.
Current nodeIn queueVisitedBFS tree edge
PseudocodeLearn Breadth-First Search (BFS) →
1queue = [source]; visited = {source}
2while queue not empty:
3  u = queue.popleft()
4  for v in neighbors(u):
5    if v not in visited:
6      visited.add(v); parent[v] = u
7      queue.append(v)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1visited = {s}; queue = [s]; dist[s] = 0
2while queue not empty:
3  u = queue.popleft()
4  for v in adj[u]:
5    if v not in visited:
6      visited.add(v); dist[v] = dist[u] + 1; parent[v] = u
7      queue.append(v)

Implementations

1from collections import deque
2 
3 
4def bfs(adj: list[list[int]], s: int) -> tuple[list[int], list[int]]:
5    """adj[u] lists neighbours of u; nodes are 0..n-1.
6    Returns (dist, parent) with dist = -1 for unreachable nodes."""
71 · Initialize distances and queue
8    n = len(adj)
9    dist = [-1] * n
10    parent = [-1] * n
11    dist[s] = 0
12    q = deque([s])
132 · Main loop
14    while q:
15        u = q.popleft()
163 · Visit neighbours
17        for v in adj[u]:
18            if dist[v] == -1:          # mark at enqueue time
19                dist[v] = dist[u] + 1
20                parent[v] = u
21                q.append(v)
224 · Result
23    return dist, parent
Walkthrough
  1. collections.deque gives O(1) popleft(); a plain list would be O(n) per pop.
  2. dist = [-1] * n is the visited set and the answer at the same time.
  3. Neighbours are marked when appended, so each node is enqueued once.
  4. The function returns a tuple; unpack with dist, parent = bfs(adj, s).
Complexity (this implementation)
time O(V + E) · space O(V)

list.pop(0) would be O(n) per dequeue — always use deque.

Language notes
  • deque is the built-in queue; queue.Queue is a thread-safe primitive with locking overhead and is not meant for algorithms.
  • while q: is the idiomatic emptiness check — a deque is falsy when empty.
  • For a dict[int, list[int]] graph, iterate adj.get(u, []) so isolated nodes without an entry do not raise KeyError.
Common mistakes in this language
  • Using list.pop(0) as the dequeue.
  • Using if not dist[v] — the source has distance 0.
  • Forgetting [-1] * n creates a list of ints (fine) but [[]] * n would alias the same inner list.
Language differences that matter here
  • Queue primitive: C++ std::queue (over std::deque) and Python collections.deque are O(1) at both ends; JavaScript/TypeScript have no deque, so the code uses an array with a head index instead of shift() (O(n)).
  • Visited encoding: all four use dist == -1 as "unvisited"; in JS/TS/Python beware truthiness — 0 is falsy, so never write if (!dist[v]).
  • C++ queue::pop() returns void; you must read front() first. Python popleft() and the JS head index return the element directly.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Queue plus visited set. On a grid with n cells, V = n and E ≤ 4n. With an adjacency matrix the time becomes O(V²).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Shortest path by edge count on an unweighted graph or grid.
  • Level-by-level processing (tree level order, "spread one step per minute").
  • Finding the nearest node satisfying a property — BFS can stop as soon as it pops one.
  • Deep graphs where recursive Depth-First Search (DFS) would overflow the call stack; BFS is naturally iterative.
Avoid it when
  • Weighted edges: BFS ignores weights. Use Dijkstra's Algorithm (non-negative) or 0-1 BFS (weights 0/1).
  • Problems that need finishing order, back-edge detection or path structure — Depth-First Search (DFS) gives those for free (cycle detection, Topological Sort, Bridges).
  • Very wide graphs where memory is the bottleneck: the queue can hold an entire level, e.g. the whole frontier of a huge implicit state space. Iterative deepening DFS trades time for O(depth) memory.

Alternatives

Depth-First Search (DFS)0-1 BFSDijkstra's AlgorithmBFS Shortest Path (Unweighted)
Compare: BFS vs DFS

Common mistakes

  • Marking visited at dequeue time instead of enqueue time — nodes get pushed many times and the queue blows up to O(E).
  • Using Array.shift() in JavaScript as the queue: each shift is O(n), making BFS O(V²). Use a head index or a deque.
  • Forgetting to seed all sources for a multi-source BFS, or giving them distance 1 instead of 0.
  • Not handling disconnected graphs when the task is "visit everything" — a single BFS only reaches one component.
  • Re-computing neighbours of a grid cell with wrong bounds checks; validate 0 <= r < R and 0 <= c < C before indexing.

Interview patterns

  • Grid BFS with a 4- or 8-direction delta array (islands, rotting oranges, walls and gates).
  • Multi-source BFS: push every source at distance 0 to compute "distance to nearest X" for all cells in one pass.
  • BFS over implicit states: word ladder (words are nodes, one-letter changes are edges), lock combinations, sliding puzzles.
  • Level-order tree traversal by processing len(queue) nodes per iteration.
  • Bipartite check by 2-colouring nodes level by level (Bipartite Check).
Interview questions on this
Mock interviews

Example problems

Number of IslandsmediumBinary Tree Level Order TraversalmediumWord LadderhardShortest Path in Binary MatrixmediumRotting OrangesmediumClone Graphmedium