Graph Traversal: BFS and DFS Explained with Code

BFS explores a graph level by level using a queue. DFS dives as deep as possible along each branch using a stack or recursion. Both run in O(V + E) time, but they answer different questions and carry different memory costs.

A graph is a collection of nodes (vertices) connected by edges. When you need to visit every node or find a path between two nodes, you have exactly two fundamental strategies: breadth-first search (BFS) and depth-first search (DFS). Every more complex graph algorithm — Dijkstra, topological sort, connected components — builds on one of these two primitives. Understanding their mechanics and trade-offs is non-negotiable for any serious programmer.

BFS vs DFS at a Glance

The table below captures the key differences. Read it once, then the code examples will make it concrete.

BFS in Python: Adjacency List

BFS uses a queue to track which nodes to visit next. Python's collections.deque gives O(1) popleft, making it the right tool here.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

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

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

    return order

# Example graph as adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B"],
    "F": ["C"],
}

print(bfs(graph, "A"))
# Output: ['A', 'B', 'C', 'D', 'E', 'F']

The visited set is populated before enqueueing, not after dequeuing. This prevents the same node from being added to the queue multiple times, which matters in dense graphs.

DFS in Python: Recursive

DFS is most naturally expressed as a recursive function. The call stack acts as the implicit stack that holds the traversal path.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    result = [node]

    for neighbor in graph[node]:
        if neighbor not in visited:
            result.extend(dfs(graph, neighbor, visited))

    return result

print(dfs(graph, "A"))
# Output: ['A', 'B', 'D', 'E', 'C', 'F']

For very deep graphs, Python's default recursion limit of 1,000 frames will cause a RecursionError. In those cases, use an explicit stack with an iterative implementation:

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

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            # Push neighbors in reverse to maintain left-to-right order
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

When to Choose BFS

Use BFS whenever you need the shortest path in an unweighted graph. Social network friend distance, word ladder puzzles, and crawling a web graph by link depth all call for BFS. Because BFS fans out from the source level by level, it guarantees that the first time it reaches a target node, it has taken the fewest possible hops.

The trade-off is memory. In a wide graph — one where each node has many neighbors — the queue can grow to hold an entire frontier layer. For a graph with branching factor b and shortest path length d, BFS can hold up to O(b^d) nodes in the queue simultaneously.

When to Choose DFS

DFS is the right choice for problems that require exploring all possibilities, not just the nearest one. Topological sorting of a DAG, detecting cycles, finding strongly connected components (Tarjan's or Kosaraju's algorithm), and generating all permutations all rely on DFS properties. DFS is also memory-efficient on tall, narrow graphs because it only holds one root-to-leaf path at a time.

One practical note: for very deep graphs with no early termination condition, DFS can spend a long time going down a dead-end branch before backtracking. Iterative deepening DFS (IDDFS) combines DFS's low memory footprint with BFS's level-by-level guarantee, but it revisits nodes.

Time and Space Complexity

Both BFS and DFS visit every vertex once and traverse every edge at most twice (once in each direction for undirected graphs), giving a time complexity of O(V + E) for both. Space complexity differs: BFS holds the frontier in a queue (worst case O(V)), while DFS holds the current path on the stack (worst case O(V) for a linear graph, but O(H) for a balanced tree where H is the height). For a balanced binary tree, DFS uses O(log V) space vs BFS's O(V/2) on the widest level.

Related: Unit Testing Fundamentals: What to Test and How — WierdX · Virtual Memory and Paging: How Operating Systems Manage RAM