What you'll learn
Quick Answer
Breadth-first search explores level by level using a queue, visiting all neighbours before going deeper, which is why it finds the shortest path in an unweighted graph. Depth-first search follows one branch as far as possible before backtracking, using a stack or recursion, which suits cycle detection, topological sorting and exhaustive path exploration. They differ only in the container used, but that difference changes both the guarantees and the memory profile.
The Only Real Difference
Both algorithms visit every reachable node exactly once, both track what they have seen, and both are O(V + E) — vertices plus edges. Written side by side, they differ in one line.
# BFS — a queue, so the OLDEST discovered node is explored next
from collections import deque
def bfs(graph, start):
visited = {start}
frontier = deque([start])
while frontier:
node = frontier.popleft() # <- FIFO
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
frontier.append(nb)
# DFS — a stack, so the NEWEST discovered node is explored next
def dfs(graph, start):
visited = set()
frontier = [start]
while frontier:
node = frontier.pop() # <- LIFO
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
frontier.append(nb)Change popleft() to pop() and breadth-first becomes depth-first. Everything else follows from that.
BFS spreads outward in rings: all nodes one step away, then all two steps away. DFS plunges down one path until it dead-ends, then backs up to the last unexplored branch.
Why Only BFS Finds the Shortest Path
This is the property that decides most real choices, and the reasoning is worth knowing rather than memorising.
BFS visits nodes in order of distance from the start. Everything at distance 1 is visited before anything at distance 2, because the queue holds them in discovery order. So the first time BFS reaches a node, it has arrived by a shortest route — no later path can be shorter, since all shorter distances were already exhausted.
DFS gives no such guarantee. It follows one branch to the end, so it might reach the target after a long wander when a two-step route existed. It finds a path, not the shortest one.
The critical caveat: this only holds for unweighted graphs, where every edge counts as one step. Once edges have different costs, the fewest-edges path may not be the cheapest, and BFS no longer answers the question. That is what Dijkstra's algorithm is for — effectively BFS with a priority queue so the cheapest frontier node is expanded first.
So: unweighted shortest path, use BFS. Weighted, use Dijkstra. Weighted with negative edges, use Bellman-Ford.
Memory Depends on the Shape of the Graph
Both are O(V + E) in time, but their space profiles are opposites, and which one is worse depends entirely on the graph.
BFS memory scales with the width of the graph, because the queue holds an entire level at once. On a wide, shallow structure — a social network where each person has hundreds of connections — that frontier explodes. A binary tree of depth 20 has about a million nodes in its last level, and BFS holds all of them.
DFS memory scales with the depth, because the stack holds only the current path. On the same wide tree, DFS holds just 20 nodes. But on a long chain of a million nodes, DFS holds all million — and recursive DFS will overflow the call stack long before that.
The practical rule: deep and narrow favours BFS; wide and shallow favours DFS. If you expect deep recursion in Python, write DFS iteratively with an explicit stack, since the default recursion limit is around 1000 and raising it is a workaround rather than a fix.
What Each Is Actually Used For
Reach for BFS when:
- You need the shortest path or minimum number of steps in an unweighted graph — maze solving, word ladders, minimum moves on a board.
- You want nodes grouped by distance, such as friends-of-friends within two hops.
- You are searching for something likely to be near the start, since BFS checks close nodes first.
- You are doing a level-order traversal of a tree, printing it row by row.
Reach for DFS when:
- You need to detect a cycle. DFS naturally exposes back-edges to nodes still on the current path.
- You need a topological sort — task scheduling, build order, course prerequisites. Push nodes as their exploration finishes and reverse the result.
- You must explore every path or backtrack, as in sudoku solvers, N-queens and maze generation.
- You are working with connected components or flood fill, where any traversal order works and DFS is simpler to write recursively.
For counting islands in a grid, either works — the question only asks how many components exist, not the route through them.
Mistakes That Cost Marks
Marking visited at the wrong moment in BFS. Mark a node when you enqueue it, not when you dequeue it. If you wait, the same node can be added several times by different neighbours before it is processed, and the queue balloons. The algorithm still terminates, but it is no longer O(V + E).
Using a list as a queue. list.pop(0) in Python and Array.shift() in JavaScript are O(n), because everything shifts down. Inside BFS that silently turns O(V + E) into something quadratic. Use collections.deque or Java's ArrayDeque.
Forgetting the visited set entirely. On a graph with cycles this loops forever. On a tree it happens to work, which is exactly why the bug survives testing and then hangs on the real input.
Assuming DFS gives shortest paths. It does not, and this is the most commonly penalised error on this topic.
Recursive DFS on deep graphs. Python's default recursion limit is about 1000 frames. A path longer than that raises RecursionError. Convert to an explicit stack rather than raising the limit.