BFS vs DFS
Use BFS when the question asks for a shortest path or a distance in an unweighted graph. Use DFS for anything about connectivity, cycles, or ordering, and whenever the recursion itself is the answer.
Both visit every reachable node exactly once and both run in O(V + E). The difference is the order, and that order is the whole reason to pick one. BFS uses a queue, so nodes come out in the order they were discovered, which is by distance from the start. DFS uses a stack, explicit or the call stack, so it runs one branch to the end before backing up.
Side by side
| Dimension | BFS | DFS |
|---|---|---|
| Data structure | Queue, first in first out | Stack, or the call stack via recursion |
| Visit order | By distance from the source | Depth first, one branch at a time |
| Shortest path | Yes, on unweighted graphs | No, the first path found is arbitrary |
| Memory | O(width), the widest level | O(depth), the longest path |
| Cycle detection | Awkward, needs parent tracking | Natural, a grey node means a back edge |
| Topological sort | Kahn's algorithm, via in-degrees | Reverse post-order, falls straight out |
| Typical failure | Runs out of memory on a wide graph | Stack overflow on a deep one |
When to pick each
BFS
- Shortest path or fewest moves in an unweighted graph, including grids and word ladders.
- Anything phrased as levels: level order traversal, minimum depth, the view from one side of a tree.
- Multi-source problems where several starting points expand together, like rotting oranges or distance to the nearest zero.
DFS
- Connected components, flood fill, counting islands.
- Cycle detection, where the three-colour scheme reads directly off the recursion.
- Topological ordering, which is just a reversed post-order.
- Backtracking, where you must undo a choice before trying the next one. BFS has no natural place to undo.
Reaching for DFS on a shortest-path question because it finds a path faster. It does find one, and it is usually not the shortest, because depth-first order has nothing to do with distance. The mirror mistake is using BFS on a weighted graph: a route with more edges can cost less, and BFS cannot see that, which is what Dijkstra's priority queue exists to fix.
Questions people ask
Is BFS always better for shortest paths?
Only when every edge costs the same. With weights, BFS can settle a node before a cheaper longer route reaches it, so you need Dijkstra for non-negative weights or Bellman-Ford when negatives are possible.
Which uses less memory?
It depends on the shape of the graph, not on the algorithm. BFS holds a whole level at once, so a wide shallow graph is expensive. DFS holds one path, so a deep narrow graph is expensive. A balanced binary tree of a million nodes costs BFS about 500,000 nodes at the widest level and DFS about 20 frames.
Can DFS be written without recursion?
Yes, with an explicit stack, and on a large graph you often have to. The recursive version is limited by the JVM stack, which overflows somewhere around ten thousand frames deep by default.