Depth-first search and breadth-first search both visit every reachable node in a graph, but they explore in opposite orders. DFS commits to one path and follows it as deep as it goes before backtracking; BFS spreads out one layer at a time, visiting every neighbor before moving further out. Same graph, same eventual coverage, very different intermediate behavior — and that difference is exactly what makes each one the right tool for different problems.
What changed in 2026
- The core algorithms are unchanged — DFS and BFS are decades old and mathematically settled — but both remain the default building blocks taught underneath more advanced graph and AI search techniques.
- BFS-style frontier expansion underpins more retrieval and agent-planning systems, where exploring everything one step away before going deeper matches the shape of tool-use and multi-hop retrieval search.
- Iterative, stack-based DFS is favored over recursive DFS more consistently now, since deep graphs can blow a call stack, and the iterative form avoids that failure mode entirely.
How each one actually explores
Graph: A -> B -> D
A -> C -> E
DFS from A: A, B, D, C, E (dives deep down one branch first)
BFS from A: A, B, C, D, E (visits all of A neighbors first)
DFS uses a stack, either the explicit call stack through recursion, or a manual stack. BFS uses a queue, always. That single data-structure choice is the entire mechanical difference between them.
DFS(node, visited):
if node in visited: return
visited.add(node)
for neighbor in node.neighbors:
DFS(neighbor, visited)
BFS(start):
queue = [start]
visited = {start}
while queue is not empty:
node = queue.popleft()
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
DFS vs BFS compared
| Property |
DFS |
BFS |
| Underlying structure |
Stack, or recursion |
Queue |
| Explores |
As deep as possible first |
Layer by layer |
| Shortest path, unweighted |
Not guaranteed |
Guaranteed |
| Memory use |
O(h), tree height |
O(w), widest layer |
| Typical use |
Topological sort, cycle detection, maze solving |
Shortest path, level-order processing |
Memory is the practical differentiator people underestimate: BFS can use far more memory than DFS on a wide, shallow graph, because it holds an entire frontier layer in the queue at once, while DFS only holds one path worth of nodes.
When each one wins
Use BFS whenever the shortest path in an unweighted graph is needed, or results are needed level by level — social network degrees of separation, web crawlers respecting depth limits, or puzzle solvers where the fewest moves matter.
Use DFS when a full path needs exploring before it can be ruled wrong, since backtracking problems like Sudoku or N-Queens are DFS with pruning, when detecting cycles or computing a topological sort, or when memory matters more than finding the shortest route.
Common pitfalls
Using DFS when shortest path is actually needed. DFS will find a path, not necessarily the shortest one. Reaching for BFS, or Dijkstra's algorithm for weighted graphs, is the correct fix.
Recursive DFS on a very deep graph. Deep recursion can hit stack limits on graphs with long chains; switch to an explicit stack-based iterative version when depth is unbounded or untrusted.
Forgetting the visited set in either algorithm. Both will loop forever on a graph with cycles without one — this is the single most common bug in hand-written graph traversal.
FAQ
Which one is faster, DFS or BFS?
Neither — both are O(V + E), visiting every vertex and edge once. The difference is exploration order and memory pattern, not asymptotic speed.
Does BFS always find the shortest path?
Only in an unweighted graph, or one where every edge has equal weight. For weighted graphs, use Dijkstra's algorithm or Bellman-Ford instead.
Is backtracking the same as DFS?
Backtracking is DFS with early termination, abandoning a branch as soon as it is known to be invalid rather than exploring it fully. Every backtracking algorithm is a DFS; not every DFS is doing backtracking.
When is iterative deepening preferable to plain BFS or DFS?
When BFS shortest-path guarantee is wanted but its memory cost cannot be afforded — iterative deepening reruns depth-limited DFS with an increasing limit, trading recomputation for lower memory use.
Where to go next