Intermediate · Module 17 · Lesson 3
Breadth-first search
Explore layers and shortest unweighted paths.
Lesson 97 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Breadth-First Search
Queue-driven layer exploration
Current
—
Queue
A
Visited
0
Order
—
Why this step happens
Start at A and place it in the queue.
The queue contains discovered nodes in nondecreasing distance from A.
Breadth-First Search (BFS): Shortest Paths in Unweighted Graphs
BFS explores graph vertices radially using a FIFO queue. In an unweighted graph, the first time a target vertex is dequeued, the distance from the source is guaranteed to be minimal. A visited set prevents infinite loops in cyclic graphs.
public int shortestPath(int start, int target, Map<Integer, List<Integer>> adj) {
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int distance = 0;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
int node = queue.poll();
if (node == target) return distance;
for (int neighbor : adj.getOrDefault(node, List.of())) {
if (visited.add(neighbor)) {
queue.offer(neighbor);
}
}
}
distance++;
}
return -1; // Unreachable
}Active Recall Checkpoint
Why should visited.add(neighbor) happen BEFORE enqueuing rather than upon dequeuing?
Show answer & explanation
Marking visited before enqueuing prevents duplicate nodes from being added to the queue by multiple adjacent parents, preventing exponential queue blowup.
Use it when
Use BFS for shortest path in unweighted graphs, word ladders, rotting oranges, connected component discovery, and bipartite verification.
Reconsider when
Reconsider when edges have non-negative weights; BFS fails to find shortest paths on weighted graphs (use Dijkstra instead).
Cost Model
Complexity & Trade-offs
When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Breadth-first search example without looking at the trace.
- Change one input condition and explain whether the Breadth-first search invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check