Overview
Breadth-first search explores every neighbor of a vertex before any of those neighbors' own outgoing edges, implemented with a queue so vertices are processed in strict discovery order, level by level outward from the start. Depth-first search does the reverse, considering a vertex's children before its siblings, plunging as deep as possible along one path before backtracking, typically implemented via recursion (using the call stack implicitly) or an explicit stack. That structural difference has a direct, provable consequence: BFS's level-by-level ordering guarantees the first time it reaches any vertex is via a shortest path in an unweighted graph, while DFS has no such property at all and can reach a target via a long path long before a much shorter one exists. Both run in O(V + E) time for an adjacency-list graph; the choice between them is about which traversal order the actual problem needs, not raw speed.
Quick Reference
| BFS | DFS | |
|---|---|---|
| Order | Neighbors before their children | Children before siblings |
| Structure | Queue | Stack (or recursion) |
| Shortest path (unweighted)? | Guaranteed | Not guaranteed |
| Natural fit for | Shortest path, level-order processing | Backtracking, cycle detection, topological sort |
Syntax
from collections import deque
def bfs(graph, start):
visited, queue = {start}, deque([start])
while queue:
v = queue.popleft()
for n in graph[v]:
if n not in visited:
visited.add(n)
queue.append(n)Examples
# DFS via recursion; the call stack does the ordering implicitly.
def dfs(graph, v, visited=None):
if visited is None:
visited = set()
visited.add(v)
for n in graph[v]:
if n not in visited:
dfs(graph, n, visited)
return visitedOnly BFS guarantees shortest path in an unweighted graph
DFS can and often does reach a target via a much longer path before a shorter one, its structure has no bias toward proximity at all. Reach for BFS specifically when "shortest path" or "closest first" is the actual requirement.
Visual Diagram
Common Mistakes
- Using DFS for a shortest-path problem, assuming any traversal that reaches the target is good enough, when only BFS's level-order guarantees the shortest path in an unweighted graph.
- Implementing DFS recursively on a very deep or very large graph and hitting a stack-depth limit, when an iterative, explicit-stack version would have avoided it.
- Forgetting to track visited vertices in either traversal, causing infinite loops on graphs with cycles.
- Assuming BFS and DFS have meaningfully different asymptotic complexity; both are O(V + E) for an adjacency-list graph, the difference is traversal order, not big-O cost.
Performance
- Both BFS and DFS run in O(V + E) time on an adjacency-list representation, visiting every vertex and edge once; neither is inherently "faster" than the other.
- Recursive DFS consumes call-stack space proportional to the deepest path explored, a real, practical constraint on very deep graphs that an explicit-stack iterative version sidesteps.
Best Practices
- Choose BFS specifically when the shortest path (in hops, for an unweighted graph) or a strict level-order traversal is the actual requirement.
- Choose DFS for backtracking-style problems, cycle detection, topological sorting, or exhaustive path exploration where traversal order along one branch matters more than proximity.
- Prefer an iterative, explicit-stack DFS over recursion when the graph could be deep enough to risk a stack-depth limit.
- Always track visited vertices explicitly in both traversals to avoid infinite loops on cyclic graphs.