Graphs
Breadth-first search vs Depth-first search
Breadth-first search and Depth-first search both explore a graph, in different ways. Breadth-first search: explore level by level with a queue. Depth-first search: go as deep as possible first, with recursion or a stack. In the worst case both take O(V + E), so the choice comes down to the other differences below.
At a glance
| Property | Breadth-first search | Depth-first search |
|---|---|---|
| Technique | Explore level by level with a queue | Go as deep as possible first, with recursion or a stack |
| Best case time | O(V + E) | O(V + E) |
| Average case time | O(V + E) | O(V + E) |
| Worst case time | O(V + E) | O(V + E) |
| Extra space | O(V) | O(V) |
| Stable (equal values keep their order) | Not applicable | Not applicable |
| In place (no extra array) | Not applicable | Not applicable |
| Needs sorted input | No | No |
When to choose each
Choose breadth-first search when
you need the fewest edges between two nodes, or the nodes level by level.
Avoid it when
the edges have different weights.
Choose depth-first search when
you need to explore every path, find connected groups or detect cycles.
Avoid it when
you need the shortest path.