BFS vs. DFS: How to Choose the Right Graph Traversal

What graph traversal means

A graph consists of vertices connected by edges. Traversal systematically visits reachable vertices while avoiding repeated work. With an adjacency-list representation, a complete traversal takes O(V + E) time and O(V) additional space, where V is the number of vertices and E the number of edges.

Mark a node as visited when it is enqueued or pushed, not only when it is removed. This prevents the same vertex entering the worklist many times, especially when multiple edges lead to it. For a disconnected graph, start a traversal from every still-unvisited vertex.

Breadth-first search (BFS)

BFS visits vertices in layers of increasing distance from a start node. A FIFO queue preserves that order, which is why BFS finds the shortest path measured in number of edges in an unweighted graph.

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

Use BFS for minimum-hop paths, level-order tree traversal, nearest-source problems, and spreading simulations. Its frontier can become wide: a tree with a broad level may require O(V) queue space.

Depth-first search (DFS)

DFS follows one branch as far as possible before backtracking. A stack gives an iterative implementation; recursion expresses the same idea but consumes call-stack space and may overflow on a very deep graph.

def dfs(graph, start):
    seen = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                stack.append(neighbor)
    return order

DFS is a natural fit for connected-component discovery, maze exploration, cycle detection, backtracking, and topological sorting. In directed graphs, cycle checks often need three states—unvisited, active on the current recursion path, and finished—because merely having visited a vertex does not prove a back edge.

Which one should you choose?

• Choose BFS when the question asks for the fewest edges, nearest node, or values by level.
• Choose DFS when exploring complete paths, detecting structural properties, or processing dependencies.
• For reachability alone, either is usually correct; consider whether a wide queue or deep call stack is safer.
• For weighted shortest paths, ordinary BFS only works when every edge has equal cost. Use Dijkstra for nonnegative weights or a suitable algorithm for the weight structure.