1Understand
The idea
BFS explores nodes in order of distance: everything 1 step away, then 2 steps, and so on. So the first time it reaches a node is along a shortest path, as long as every edge has the same cost. Starting from several sources at once finds the distance to the nearest source.
Intuition
BFS explores in order of distance: everything 1 step away, then 2, and so on. The first time you reach a node is along a shortest path, as long as every edge has the same cost.
Multi-source BFS starts with several nodes already in the queue (distance 0) and finds distance to the nearest source in one go, rotting oranges, walls and gates.
Use a queue; mark visited when enqueuing to avoid duplicate entries.
What you will be able to do
- Mark visited when enqueuing
- Run multi-source BFS
When to use it
- Minimum number of steps / moves
- Shortest path with equal edge cost
- Spread from several sources at once
2See it
Walkthrough
Shortest path in unweighted graph
Start 0, edges 0-1, 0-2, 1-3, BFS layers are distances.
1 / 4
Queue [0], dist[0]=0. Pop front; enqueue unseen neighbors.
Live template
Line 1 active
Complexity: time O(V + E), space O(V)
O(V + E) time, O(V) space. DFS does not give shortest paths on unweighted graphs. Dijkstra is for weighted edges; using it on unit weights works but is heavier than BFS.
Read the walkthrough as text
Shortest path in a binary matrix / grid. From top-left to bottom-right on 4-directional open cells.
- Queue
(0,0)with dist1(or0depending on counting). Mark visited. - Pop cells; enqueue unvisited open neighbours with
dist + 1. - First time you pop the target, that dist is minimal, return it.
- If the queue empties first, unreachable.
Multi-source variant: enqueue all gates first with dist 0, then BFS fills rooms.
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Shortest path on a grid
Example. Minimum steps from top-left to bottom-right through 0 cells.
How. BFS layers; first time you reach destination is shortest step count.
Multi-source BFS (rotting oranges)
Example. Minutes until all oranges rot.
How. Enqueue all rotten cells at distance 0; BFS expands simultaneously.
State-space BFS (word ladder, open the lock)
Example. Shortest sequence of moves to reach target string.
How. Queue (state, dist); visit neighbours; unvisited enqueued with dist+1.
0-1 BFS with a deque
Example. Shortest path with weights only 0 or 1.
How. Deque front push for 0-weight, back for 1; still O(V+E).
BFS with extra state (keys, obstacles)
Example. Shortest path in grid with keys and doors.
How. State = (row, col, key bitmask); mark visited per full state.
Distances from two sources
Example. Nearest 0 and nearest 1 in a binary matrix.
How. Multi-source BFS from all 0s (and separately all 1s) to fill distance grids.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Visited marked late
Why it happens. Marking visited when dequeuing allows duplicate enqueue.
How it fails. Grid BFS: same cell enqueued many times, queue explodes and time blows up.
Fix. Mark dist/visited when pushing to the queue (first discovery), not when popping.
DFS for shortest path
Why it happens. DFS finds *a* path, not the shortest in unweighted graphs.
How it fails. Maze: DFS returns length 9 path while BFS would find length 3.
Fix. Equal edge weight → BFS layers give shortest steps; DFS only for reachability/exhaustive search.
State too small
Why it happens. Position alone cannot distinguish locked doors or keys already held.
How it fails. Revisit (r,c) without key bitmask, you skip a necessary state that unlocks a door.
Fix. State includes whatever changes moves: keys bitmask, remaining energy, etc.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.