Breadth-First Search (BFS)

Definition: A graph traversal algorithm that explores nodes level-by-level, visiting all immediate neighbors before moving to the next distance layer.

How It Works

BFS uses a Queue (FIFO) to control traversal order:

queue = [start]
visited = {start}
while queue is not empty:
    node = queue.dequeue()
    for neighbor in node.neighbors:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.enqueue(neighbor)

Because the queue processes nodes in the exact order they were discovered, and every neighbor of the current “layer” is enqueued before any node from the next layer is dequeued, BFS exhausts an entire distance layer before advancing to the next one. This layer-by-layer property is what guarantees shortest-path-in-edges correctness for unweighted graphs.

The visited set is marked at enqueue time, not dequeue time. Marking at dequeue time instead allows the same node to be enqueued multiple times before it’s first processed, wasting work and, in graphs with certain structures, breaking correctness of distance tracking.

To reconstruct the actual shortest path, not just its length, store a parent[node] pointer the first time each node is discovered (enqueued). Walking parent pointers backward from the target to the source, then reversing that list, recovers the full path in O(path length) time.

Complexity Analysis

Metric	Complexity
Time	O(V + E)
Space	O(V), worst case a wide, shallow graph holds an entire layer in the queue
Shortest path (unweighted)	Guaranteed correct, in edge count

V is the number of vertices, E the number of edges; every vertex is enqueued/dequeued once and every edge is examined once across the whole traversal.

Why It Matters

Guarantees finding the shortest path in unweighted graphs between a start node and any reachable target. This guarantee fails for weighted graphs, where Dijkstra Algorithm is required instead, since BFS only counts edge hops and ignores weight entirely.
Layer-by-layer exploration makes BFS the natural fit for any problem phrased as “minimum number of steps/moves/hops,” e.g. word ladder puzzles, minimum moves on a game board, or degrees of separation in a social graph.
Bidirectional BFS, searching simultaneously from both the source and the target and stopping when the two frontiers meet, cuts the effective search space from O(b^d) to roughly O(b^(d/2)) for branching factor b and depth d, a large practical win in huge graphs like social networks or web crawls.

Common Pitfalls

Consumes significant memory when exploring graphs with a large branching factor, since an entire frontier layer can sit in the queue simultaneously; on a graph where each node has hundreds of neighbors, that queue can grow very large before any dequeuing happens.
Marking nodes visited at dequeue time instead of enqueue time allows the same node to be added to the queue multiple times, wasting work and, in some implementations, breaking correctness of the shortest-distance computation.
Using BFS on a weighted graph and assuming it still finds the shortest path; it counts edge hops only, so a 1-hop path with weight 100 will be preferred over a 3-hop path with total weight 3.
Forgetting the visited check entirely causes infinite loops on any graph containing a cycle, since the same node keeps getting re-enqueued forever.
Applying BFS to a directed graph without checking edge direction, silently treating it as undirected and exploring edges that don’t actually exist in that direction.

Comparison

	BFS	DFS	Dijkstra
Traversal order	Level by level	Deep, then backtrack	Priority by cumulative distance
Data structure	Queue	Stack / recursion	Priority queue (min-heap)
Shortest path guarantee	Yes, unweighted only	No	Yes, non-negative weights
Memory profile	Can hold a wide frontier	Holds one root-to-leaf path	Holds a priority queue of frontier nodes
Typical use	Shortest hops, level order	Cycle detection, topological sort	Weighted shortest path

Example

Finding the fewest flight connections between two airports is a textbook BFS use case. On a graph with edges A-B, A-C, B-D, C-D, D-E, BFS from A explores layer 0 {A}, layer 1 {B, C}, layer 2 {D}, layer 3 {E}, reaching E in 3 hops via either A-B-D-E or A-C-D-E, both discovered simultaneously since BFS finishes exploring all of layers 1 and 2 before touching layer 3 at all.

Layer 0: A
Layer 1: B, C     (A's neighbors)
Layer 2: D        (via B or C, whichever is dequeued first)
Layer 3: E        (via D)

Queue State, Step by Step

Tracing the exact queue and visited-set contents for the same graph (A-B, A-C, B-D, C-D, D-E), starting BFS from A:

init:        queue=[A]        visited={A}
dequeue A:   queue=[B,C]      visited={A,B,C}   (enqueue B, C; parent[B]=A, parent[C]=A)
dequeue B:   queue=[C,D]      visited={A,B,C,D} (enqueue D; parent[D]=B; C already visited, skip)
dequeue C:   queue=[D]        visited={A,B,C,D} (D already visited, skip; no new work)
dequeue D:   queue=[E]        visited={A,B,C,D,E} (enqueue E; parent[E]=D)
dequeue E:   queue=[]         done

Walking parent backward from E: E -> D -> B -> A, reversed to A -> B -> D -> E, the shortest path in 3 hops.

Variants

0-1 BFS: a deque-based variant for graphs whose edge weights are only 0 or 1, pushing 0-weight edges to the front of the deque and 1-weight edges to the back. This finds shortest paths in O(V + E) without needing a full priority queue like Dijkstra.
Multi-source BFS: seed the queue with several starting nodes simultaneously (all marked visited at distance 0) instead of one, useful for problems like “distance from the nearest of several fires spreading through a grid.” Tracing a tiny grid with fires at (0,0) and (2,2):
```
init queue=[(0,0,dist=0), (2,2,dist=0)]   both marked visited
dequeue (0,0): enqueue its unvisited neighbors at dist=1
dequeue (2,2): enqueue its unvisited neighbors at dist=1
dequeue each dist=1 cell: enqueue their unvisited neighbors at dist=2
```
Every cell ends up with its distance to the nearest fire, computed in a single BFS pass rather than running BFS separately from each source and taking the minimum.
BFS on an implicit graph: many problems (word ladder, sliding puzzle, minimum knight moves) never build an explicit adjacency list; neighbors are generated on the fly from the current state, and BFS explores the implicit state-transition graph directly.

FAQ

Does BFS work on weighted graphs at all? It runs without error, but the result is meaningless as a shortest path unless every edge has equal weight; BFS only ever counts hops, never sums weights, which is precisely the gap Dijkstra Algorithm fills.

Why use a queue instead of a stack? A queue enforces FIFO processing order, guaranteeing every node in the current distance layer is dequeued before any node from the next layer is even considered. Swapping in a stack turns the traversal into DFS, losing the shortest-path guarantee entirely.

Real-World Systems

Social networks compute “degrees of separation” (e.g. LinkedIn’s “2nd/3rd connection” labels) using BFS-style layer expansion from a given user, since each layer directly corresponds to a degree of separation.
Web crawlers commonly explore links in roughly BFS order from seed pages, prioritizing broad coverage of nearby pages before following long chains deep into a single site.
Network broadcast and flooding protocols (e.g. how a routing update propagates hop by hop) mirror the BFS layer-expansion pattern, even when no explicit queue data structure is involved.
Puzzle solvers (word ladder, sliding puzzle, Rubik’s Cube solvers restricted to a shallow depth) use BFS over an implicit state graph specifically because it guarantees the minimum number of moves.

Referenced by

Dig deeper

Spot an error in this note?