BFS vs DFS: Choosing a Graph Traversal for Shortest Paths, Components and Cycles

By 0xmote · May 25, 2026 · 16 min read · Updated Sep 27, 2026 Intermediate Tutorial

Key takeaways

How breadth-first and depth-first search traverse graphs and trees, why BFS gives shortest paths only on unweighted graphs, where visited marking goes, and the recursion and ordering bugs that break interview solutions.

Introduction

BFS (breadth-first search) and DFS (depth-first search) are the two basic ways to walk a graph or tree. Both visit every reachable node exactly once and both run in O(V + E) time, so the choice between them is almost never about speed. It comes down to the order in which nodes are discovered, and that order decides whether you get shortest distances, a natural backtracking structure, or a program that runs out of stack.

This post covers both traversals in Python, explains why BFS yields shortest paths, and goes through the implementation details that most often break interview solutions: where to mark nodes visited, recursion limits, and the subtle difference between recursive and stack-based DFS.

BFS (Breadth-First Search)

What BFS does

BFS visits nodes in order of distance from the start: first the start node, then everything one edge away, then everything two edges away, and so on. The ripple-in-a-pond picture is accurate: the frontier expands one ring at a time.

    1
   / \
  2   3
 / \
4   5
BFS order: 1 → 2 → 3 → 4 → 5 (level by level)

Python implementation

BFS keeps the frontier in a FIFO queue. In Python that means collections.deque, because list.pop(0) shifts every remaining element and costs O(n) per call, which quietly turns an O(V + E) algorithm into O(V²).

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

# Graph (adjacency list)
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}
print(bfs(graph, 1))  # [1, 2, 3, 4, 5]

Why BFS gives shortest paths

The guarantee comes from a queue invariant. When a node at distance d is dequeued, every node still in the queue has distance d or d + 1, and all distance-d nodes come before all distance-d + 1 nodes. So the first time BFS discovers a node, it discovers it through a shortest route; any later route would come from a node dequeued later, which is at least as far away.

That argument depends on every edge costing the same. Once edges carry weights, a path with three cheap edges can beat a path with one expensive edge, and BFS will happily report the one-edge path. For weighted graphs use Dijkstra (non-negative weights), 0-1 BFS with a deque (weights of only 0 and 1), or Bellman-Ford (negative weights).

Shortest distance

Storing the distance in the visited dictionary doubles as the visited set:

def bfs_shortest_path(graph, start, end):
    dist = {start: 0}  # node -> distance from start
    queue = deque([start])

    while queue:
        node = queue.popleft()

        if node == end:
            return dist[end]

        for neighbor in graph[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)

    return -1  # unreachable

print(bfs_shortest_path(graph, 1, 4))  # 2 (1 → 2 → 4)

If you also need the path itself, store parent[neighbor] = node at the same place you set the distance, then walk back from end to start and reverse.

Mark visited on enqueue, not on dequeue

This is the most common BFS bug I see in otherwise correct solutions. If you only add a node to visited when you pop it, the same node can be pushed once by each neighbor that sees it before it is processed. The answer stays correct, so small tests pass, but the queue grows far beyond V. Counting pushes on an open n × n grid with 4-way moves:

Grid	Mark on enqueue	Mark on dequeue
10 × 10	100 pushes	181 pushes
100 × 100	10,000 pushes	19,801 pushes

On an open grid that is roughly double the work; on denser graphs, where a node has many neighbors discovered at the same level, the duplication is worse. Marking on enqueue guarantees each node enters the queue exactly once, and distances are still correct because of the invariant above.

DFS (Depth-First Search)

What DFS does

DFS follows one branch as deep as it can, then backtracks to the most recent node that still has unexplored neighbors. It is the maze strategy of keeping a hand on one wall until you hit a dead end.

    1
   / \
  2   3
 / \
4   5
DFS order: 1 → 2 → 4 → 5 → 3 (depth first)

Recursive implementation

def dfs_recursive(graph, node, visited, result):
    visited.add(node)
    result.append(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)

visited = set()
result = []
dfs_recursive(graph, 1, visited, result)
print(result)  # [1, 2, 4, 5, 3]

Recursion makes DFS read like its definition, and backtracking falls out for free: when a call returns, you are back at the parent with its local state intact. That is why problems like “all paths”, permutations and N-Queens are nearly always written recursively.

The cost is the call stack. CPython’s default recursion limit is 1000 (sys.getrecursionlimit()), and exceeding it raises:

RecursionError: maximum recursion depth exceeded

A balanced binary tree with a million nodes is only about 20 levels deep, so trees are rarely a problem. Grids and linked-list-shaped graphs are different: a 300 × 300 grid of land can produce a DFS path tens of thousands of cells long. sys.setrecursionlimit(10**6) often works on judges, but it only lifts Python’s own check; the underlying C stack can still overflow and crash the interpreter without a traceback. On large inputs, an explicit stack is the safer choice.

Iterative implementation (explicit stack)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        result.append(node)

        # Push in reverse so the first neighbor is popped first
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

    return result

print(dfs_iterative(graph, 1))  # [1, 2, 4, 5, 3]

Two details make this match the recursive version. The neighbors are pushed in reverse so that the first neighbor ends up on top of the stack. And a node is marked visited when it is popped, which means a node can sit in the stack more than once (the stack may hold O(E) entries) and the if node in visited: continue check skips the stale copies.

The mark-on-push trap for iterative DFS

It is tempting to reuse the BFS habit and mark nodes when pushing them. That still visits every reachable node once, so it is fine for reachability or counting components, but it no longer produces a depth-first order. Take this graph:

g = {1: [2, 3, 4], 2: [1, 4], 3: [1], 4: [1, 2]}

Recursive DFS from 1 visits [1, 2, 4, 3]: from 2 it goes deeper to 4. The mark-on-push stack version visits [1, 2, 3, 4], because 4 was already marked when it was pushed as a neighbor of 1, so 2 never claims it. Any algorithm that relies on DFS tree structure, such as discovery/finish times, bridges, articulation points or topological sort by finish order, can silently give wrong answers with this variant. I find this one of the harder bugs to catch in review, because the code still looks like a DFS and it usually passes the sample cases; it only fails on a graph with a “shortcut” edge like 1 → 4 above.

BFS vs DFS Comparison

Feature	BFS	DFS
Frontier structure	Queue (FIFO)	Stack (LIFO) or call stack
Order	By distance from start	One branch to the end, then backtrack
Shortest path (unweighted)	Yes	No
Extra memory	O(width of the widest level)	O(depth of the current path)
Typical style	Iterative	Recursive, or iterative for deep inputs
Time	O(V + E)	O(V + E)

The memory row is where “DFS uses less memory” rules of thumb break down. On a wide, shallow graph, such as a tree with a large branching factor, BFS holds an entire level at once while DFS holds a single root-to-leaf path. On a long, thin graph the situation reverses: DFS’s stack becomes as long as the graph while BFS’s queue stays small. Think about the shape of the input rather than assuming one is always cheaper.

BFS fits minimum steps or moves in an unweighted graph, level-order output, and “nearest X from here” queries. Multi-source BFS (push all sources at distance 0) handles “distance to the nearest gate/rotten orange/exit” problems in a single pass.

DFS fits enumerating all paths or configurations (backtracking), connected components and flood fill, cycle detection, and topological order.

Problem Solving

Problem 1: Maze shortest path (BFS)

from collections import deque

def maze_escape(maze):
    """
    Shortest path length from (0,0) to (n-1,m-1), counting cells.
    1 = walkable, 0 = wall.
    """
    n, m = len(maze), len(maze[0])
    queue = deque([(0, 0, 1)])  # (row, col, cells walked)
    visited = {(0, 0)}
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while queue:
        r, c, dist = queue.popleft()
        if r == n - 1 and c == m - 1:
            return dist

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < n and 0 <= nc < m and
                    maze[nr][nc] == 1 and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, dist + 1))

    return -1

maze = [
    [1, 0, 1, 1, 1],
    [1, 0, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 0, 1]
]
print(maze_escape(maze))  # 14

The only route goes down the left column, along the bottom to column 2, up to the top row and then down the right column: 14 cells including start and end. Whether the answer counts cells or moves (13 here) is the classic off-by-one in these problems, so read the statement for which one it wants and initialize dist to 1 or 0 accordingly.

Problem 2: Number of islands (DFS)

def count_islands(grid):
    """Count 4-directionally connected regions of 1s."""
    if not grid:
        return 0

    n, m = len(grid), len(grid[0])
    visited = set()
    count = 0

    def dfs(r, c):
        if (r < 0 or r >= n or c < 0 or c >= m or
                grid[r][c] == 0 or (r, c) in visited):
            return
        visited.add((r, c))
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    for i in range(n):
        for j in range(m):
            if grid[i][j] == 1 and (i, j) not in visited:
                dfs(i, j)
                count += 1

    return count

grid = [
    [1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]
]
print(count_islands(grid))  # 3

The traversal order does not matter here, only that each land cell is reached once, so BFS works equally well. The recursive version is the shortest to write but is exactly the case that hits RecursionError on a large all-land grid. If the constraints allow grids of several hundred cells per side, switch the inner dfs to an explicit stack or a BFS before submitting.

Problem 3: All paths (DFS with backtracking)

def all_paths(graph, start, end):
    """All simple paths from start to end."""
    result = []

    def dfs(node, path):
        if node == end:
            result.append(path[:])  # copy, the list keeps changing
            return
        for neighbor in graph[node]:
            if neighbor not in path:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()  # backtrack

    dfs(start, [start])
    return result

dag = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(all_paths(dag, 1, 4))  # [[1, 2, 4], [1, 3, 4]]

Notice there is no global visited set. A global set would stop the second path from ever reaching node 4. Here “visited” means “on the current path”, and it is undone on the way back. path[:] matters too: appending path itself stores a reference to a list that is emptied by later pop() calls, and you end up with a result full of identical lists. neighbor not in path is O(length of path); for long paths, keep a parallel set that you add to and remove from alongside the list.

Implementation Details That Matter

Grid directions. Keep moves in a list and loop over it rather than writing four if blocks, which is where copy-paste typos in row/column indices creep in:

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 4-way
# 8-way adds diagonals:
# [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

Level-by-level BFS. When the output is grouped by level (binary tree level order, “minimum number of rounds”), snapshot the queue length before processing a level:

while queue:
    level_size = len(queue)
    for _ in range(level_size):
        node = queue.popleft()
        # process node, enqueue children
    # one full level done here

Undirected graphs and cycles. In an undirected graph every edge appears twice, so “I reached a visited node” does not by itself mean there is a cycle: you may just be looking back along the edge you came from. Pass the parent into the DFS and ignore it. In directed graphs, use three states (unvisited, on the current path, finished); only an edge to an “on the current path” node is a cycle.

Disconnected graphs. A single traversal from one start covers one component. To process the whole graph, loop over every node and start a new traversal from each unvisited one, as the islands example does.

Choosing between BFS and DFS

BFS uses a queue, visits nodes by distance, and gives shortest paths in unweighted graphs. Mark nodes visited when you enqueue them.
DFS uses recursion or a stack, goes deep first, and is the natural fit for backtracking, components and cycle detection. Watch Python’s recursion limit.
Both are O(V + E) time. Memory depends on the input’s shape: BFS pays for width, DFS pays for depth.
For an explicit-stack DFS that behaves like the recursive one, push neighbors in reverse and mark nodes visited when popped.

Practice problems

Beginner: LeetCode 104 (Maximum Depth of Binary Tree), 111 (Minimum Depth of Binary Tree), 733 (Flood Fill)
Intermediate: LeetCode 200 (Number of Islands), 207 (Course Schedule), 127 (Word Ladder)
Advanced: LeetCode 301 (Remove Invalid Parentheses), 126 (Word Ladder II), 417 (Pacific Atlantic Water Flow)

LeetCode 111 is a good test of the ideas above: BFS can stop at the first leaf it dequeues, while DFS has to explore the whole tree to be sure it found the shallowest one.

Frequently Asked Questions

Q. Which should I reach for first, BFS or DFS?

A. If the question asks for the minimum number of steps, moves or edges in an unweighted graph, use BFS. If it asks whether something is reachable, how many components exist, or to enumerate every path or configuration, DFS is usually shorter to write. For plain reachability both work.

Q. Does BFS find shortest paths in weighted graphs?

A. No. BFS counts edges, not weights. With non-negative weights use Dijkstra; with weights of only 0 and 1 a deque-based 0-1 BFS works; with negative weights you need Bellman-Ford.

Q. Why does my recursive DFS crash on a large grid in Python?

A. CPython limits recursion depth to 1000 by default, and a snake-shaped path through a large grid can be far deeper than that, so you get RecursionError: maximum recursion depth exceeded. Raise the limit with sys.setrecursionlimit or rewrite the DFS with an explicit stack.

Q. Is iterative DFS with a stack exactly the same as recursive DFS?

A. Only if you mark a node visited when you pop it, not when you push it. Marking on push is fine for reachability and counting components, but it can produce a different visiting order and different parent edges than recursive DFS.