Algorithms · intermediate
Breadth-first search
Breadth-first search explores a graph in nondecreasing number of edges from a start vertex by processing a FIFO queue of discovered vertices.
Why it matters
BFS finds shortest path lengths in unweighted graphs and naturally discovers layers, connected regions, and minimum-step states.
Mental model
How to reason about breadth-first search
The queue is a moving frontier: all vertices at distance d are removed before vertices at distance d+1, so the first discovery fixes the minimum edge count.
Analogy
Ripples spread from a dropped stone in rings; every point one step away is reached before any point two steps away.
Examples
See the boundary, not just the happy path
Worked example · Minimum transfers
stations are vertices; direct routes are unweighted edgesBFS layers correspond to transfer counts, so the first visit to a station gives the fewest routes from the origin.
Worked example · Avoid repeated work
mark neighbor visited when enqueueing itMarking on discovery prevents multiple parents from adding the same vertex to the queue.
Useful contrast · Weighted edges
one edge costs 1 minute, another costs 90 minutesBFS minimizes edge count, not summed weight. Dijkstra's algorithm is needed for nonnegative unequal weights.
Common mistakes
Misconceptions to remove early
Marking visited only when dequeued
The same vertex can be enqueued many times before its first removal, inflating memory and work. Mark it when first enqueued.
Forgetting disconnected components
A search from one source visits only its reachable component. To traverse an entire disconnected graph, start BFS again from each unvisited vertex.
Quick check
Can you predict the result?
1. Which frontier structure gives BFS its layer-by-layer order?
- • A FIFO queue
- • A LIFO stack
- • A hash value sorted descending
2. Why does BFS find minimum-edge paths in an unweighted graph?
Keep building