What it is
Breadth-first search explores a graph outward from one or more starting nodes, visiting everything at distance 1 before anything at distance 2, and so on, using a queue to hold the frontier. Because it expands in strict distance order, the first time it reaches a node is guaranteed to be by a shortest path, as long as every edge costs the same (or the "edges" all represent one unit of time, like one minute of spreading or one bus ride). It also naturally groups nodes by level, which is useful any time you need "everything at depth d" rather than just the shortest distance to one target.
When it applies
- You need the shortest path or fewest steps between nodes in an unweighted graph, or the fewest "moves" in a state space where every move counts equally (word transformations, puzzle moves, bus boardings).
- You need to process a tree or graph level by level, or need every node at exactly some fixed distance from a source.
- Rot, fire, infection, or influence spreads outward simultaneously from multiple sources and you need the time until everything is reached — start the queue with every source at once (multi-source BFS).
- Once edges have different weights, plain BFS no longer guarantees the shortest path — reach for a priority-queue approach (Dijkstra-style) instead. And if you only need to know whether two nodes are connected at all, either BFS or DFS works, so don't reach for a queue out of habit if a simpler stack or recursion would do.
Tells in the problem
- "Shortest path" or "minimum number of steps/moves/transformations" in a graph or grid where every step is worth the same.
- "Level order," "distance k from a node," or grouping nodes by their depth.
- A grid where a value spreads to its neighbors "every minute" from several starting cells at once.
- "At most k stops/hops," where the state includes both a location and a hop count, not just a location.
- Nodes are connected by an indirect, shared property (a word one letter away, a route sharing a stop) rather than an explicit adjacency list, meaning you build the graph as you search.
The classic mistake
Marking a node visited when it's dequeued rather than the moment it's enqueued — this lets the same node get pushed onto the queue many times before it's ever processed, which doesn't break correctness but silently turns a linear-time search into one that's exponential or that never terminates on a graph with cycles. It happens because visiting-on-dequeue feels natural when you're thinking "process, then look at neighbors," but by then several other paths may already have queued the same node again. Catch it by checking, right where you enqueue a neighbor, that the visited set is updated in that same line — not later when it comes off the queue.
Questions to start with
- Binary Tree Level Order Traversal — the purest form of level-by-level processing, no distance calculation needed yet.
- Number of Islands — BFS (or DFS) as a connected-component counter on a grid, before shortest-path reasoning enters.
- Rotting Oranges — multi-source BFS, where the queue starts with several cells at once instead of one.
- Word Ladder — the graph isn't given explicitly; you generate neighbors on the fly, and shortest-path counting becomes the actual goal.
- Cheapest Flights Within K Stops — adds a hop-count limit to the state, showing where plain shortest-path BFS needs to track more than just the node.