← All patternsGraph BFS · template
Pattern · Graphs
Graph BFS
Explore from a start node in rings of increasing distance using a queue and a visited set.
Time O(V + E) · Space O(V)
Taught in Module 21: Breadth-First Search
Think of it like this
Ripples on a pond: everything one step away is reached first, then two steps, and so on.
Clues that point here
- → Shortest path with equal edge weights
- → Minimum number of moves or steps
- → Spread from several sources at once (rotting oranges)
- → Word ladder
Not this pattern when
- ✕ Edges have different weights (Dijkstra)
- ✕ You need all paths (DFS/backtracking)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Queue<Integer> q = new ArrayDeque<>();
boolean[] seen = new boolean[n];
q.offer(start); seen[start] = true;
int steps = 0;
while (!q.isEmpty()) {
for (int size = q.size(); size > 0; size--) {
int node = q.poll();
if (node == goal) return steps;
for (int next : graph.get(node)) {
if (!seen[next]) { seen[next] = true; q.offer(next); }
}
}
steps++;
}
return -1;Common versions
- Shortest path in a binary matrix
- Rotting oranges (multi-source)
- Word ladder
- Open the lock
- 0-1 BFS
Practice problems with this pattern
20.1Find Center of Star GraphEasymain pattern20.2Find the Town JudgeEasymain pattern20.3Find if Path Exists in GraphEasymain pattern20.5Maximal Network RankMediummain pattern21.1Rotting OrangesMediummain pattern21.2Shortest Path in Binary MatrixMediummain pattern21.301 MatrixMediummain pattern21.4Open the LockMediummain pattern21.5Nearest Exit from Entrance in MazeMediummain pattern21.6Word LadderHardmain pattern21.7Minimum Obstacle Removal to Reach CornerHardmain pattern23.5Detect Cycles in 2D GridMediummain pattern22.1Number of IslandsMediumalso uses it24.6Minimum Height TreesMediumalso uses it30.4Coin ChangeMediumalso uses it30.7Perfect SquaresMediumalso uses it32.9Shortest Path Visiting All NodesHardalso uses it33.3Jump Game IIMediumalso uses it