BFS vs DFS

Suppose D is the place you are searching for in the small example above. DFS reaches it sooner when it follows B first. That does not make DFS the better choice for every search: a different target or a longer branch changes what happens. To choose, distinguish finding any route from finding one with the fewest steps.

A graph describes places or objects as nodes and their connections as edges. The small example is a tree-shaped graph, with no route back to an earlier node. The diagram expands the same idea to seven nodes: both panels show the same connections and start point, but number the visits differently.

How the next node is chosen#

Both searches keep work waiting. BFS takes the oldest waiting node first. That is a queue: first in, first out, often shortened to FIFO. DFS takes the newest waiting node first. That is a stack: last in, first out, or LIFO. The waiting collection is often called the frontier.

For the small example, processing A adds B and C to the BFS queue. Processing B then adds D behind C. The queue now contains C followed by D, so C is visited next. The full order is A, B, C, D.

For DFS to choose B first, put C on the stack before B. B is then the next item removed. Processing it puts D on top of the waiting C, so the order becomes A, B, D, C. Reversing the order of neighbours when adding them to a stack preserves which neighbour should be explored first.

The Python functions below return visit order, not a reconstructed path. Each graph value must be an ordered list of neighbours, and every reachable node must appear as a key, even when its list is empty. Both functions track visited nodes so a cycle does not make them process the same node forever.

def bfs(start, graph):
    from collections import deque

    order, seen = [], {start}
    frontier = deque([start])
    while frontier:
        node = frontier.popleft()      # oldest pending node
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return order

def dfs(start, graph):
    order, seen = [], set()
    frontier = [start]
    while frontier:
        node = frontier.pop()          # newest pending node
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in seen:
                frontier.append(neighbor)
    return order

In BFS, popleft() removes the oldest entry. Python’s deque supports this operation in approximately constant time. Using a list and pop(0) instead shifts the remaining entries; over a traversal, those shifts can add up to quadratic work in the number of nodes.

The DFS function does more than replace popleft() with pop(). It records a node as visited when removing it from the stack, and adds neighbours in reverse. This lets the current branch reach a node even when another pending branch has already placed it on the stack. A later duplicate is skipped. The result matches recursive DFS’s visit order for the same neighbour order.

Marking every neighbour visited when it is first pushed is a different traversal on a general graph. It still finds reachable nodes, but an earlier pending branch can claim a node before the current branch reaches it. That distinction matters when comparing exact orders or building an algorithm that relies on a genuine depth-first search tree.

The diagram uses recursive DFS on a tree; the explicit-stack version produces the same order. For another view of BFS on trees, follow the level-order traversal.

Why BFS finds a path with the fewest edges#

In the example, D can enter the queue while C is still waiting. BFS does not have to finish discovering one distance layer before discovering anything in the next. What matters is processing order: C was already waiting, so it is processed before D.

The same rule holds at each distance from the start. All nodes at distance one are processed before those at distance two, and so on. When BFS first discovers a node, a route with fewer edges would already have been found from an earlier layer. That is why the first discovery provides a fewest-edge route.

To return that route, record which node first discovered each new node, then follow those predecessor links backwards from the target. The example functions only return the order of visits; they do not yet store those links.

DFS does not process nodes by distance. It can follow a long branch to the target before trying a short alternative. Its first route might happen to be shortest, but that is not a guarantee.

Now change the question from fewest edges to lowest cost. One direct edge might cost 100, while two edges cost 1 each. BFS favours the direct route by edge count even though its total cost is higher. With non-negative weights, Dijkstra’s algorithm uses a priority queue to choose by accumulated cost instead. Try that distinction in the Dijkstra visualiser. Negative weights need a different shortest-path method.

Choose by the question and the graph#

For a complete traversal with adjacency lists, both functions take O(V + E) time: work grows with the number of nodes V and edges E. Each node’s neighbours are inspected once. The simple DFS can place a node on its stack more than once, but each placement comes from an examined edge; skipping duplicate entries keeps the total within that bound.

Memory depends on the implementation too. BFS stores each discovered node once in its queue and visited set, so its extra space is O(V), including the returned order. This DFS can keep several pending entries for the same node and therefore needs O(V + E) extra space in the worst case. A version that keeps an iterator for each active node can use O(V) instead, while preserving recursive behaviour.

The familiar comparison between a wide BFS queue and a deep DFS call stack is most useful for trees when you are not also storing every visited node or the full result. Recursive DFS then keeps a path of depth h; BFS may keep a level of width w. Do not transfer those smaller bounds to a graph implementation that also stores a visited set.

Recursive DFS has another limit. In Python, a sufficiently deep chain normally raises RecursionError. Raising the interpreter’s recursion limit too far can risk a crash; it is not a general solution for arbitrary depth. An explicit stack avoids recursive calls, although it still consumes memory.

A cycle without visited-state handling can cause repeated work in either search. An iterative version may keep adding and removing nodes without finishing. A recursive version normally reaches the recursion limit rather than running silently forever. The functions above prevent repeated processing, but their visited set alone is not a complete cycle detector.

For example, detecting a directed cycle with DFS requires distinguishing a node on the current active branch from one whose exploration has finished. Topological ordering also depends on completion order and requires a directed graph with no cycles. Those algorithms need more information than the visit-order list returned here. The topological-sort guide compares this finish-order method with Kahn’s ready set and lets you add a dependency that blocks the remaining tasks.