Breadth-First Search vs Depth-First Search
Breadth-First Search and Depth-First Search are both graph traversal. Play them side by side below, then see exactly where they diverge.
Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.
Breadth-First Search
Full topicExplore layer by layer with a queue. Discovers shortest paths in unweighted graphs.
DEQUEUE -> VISIT -> ENQUEUE unvisited neighbours. The frontier expands in rings. Queue drawn alongside.
Depth-First Search
Full topicGo as deep as possible before backtracking. The recursion stack is the frontier.
DESCEND along an edge -> dead end -> BACKTRACK. The call stack grows and shrinks beside the graph.
How they differ
Both visit everything reachable from the start in O(V + E). What differs is which vertex they take next. Breadth-first search takes the oldest from a queue, so it spreads out layer by layer and reaches each vertex by the fewest edges, which is why it finds shortest paths in an unweighted graph. Depth-first search takes the newest, from the recursion stack, so it follows one path as deep as it goes before backtracking.
The run shown here takes 8 steps for Breadth-First Search and 10 steps for Depth-First Search (Depth-first from 0). That count moves with the input - use the example tabs above either player to see it change.
| Cost | Breadth-First Search | Depth-First Search |
|---|---|---|
| best | O(V + E) | O(V + E) |
| average | O(V + E) | O(V + E) |
| worst | O(V + E) | O(V + E) |
| space | O(V) | O(V) |