DFS vs BFS: Which Graph Traversal Should You Use?

Use BFS when you need the shortest path in an unweighted graph or a clean level-by-level order, and use DFS when you care about paths, cycles, or topological order and want to spend less memory on wide graphs. Both visit every vertex and edge once, so they share the same O(V + E) running time. The only real difference is the order they visit nodes and how much memory that order costs.

What actually differs between DFS and BFS?

The frontier is the set of nodes you have discovered but not yet expanded, and the only structural difference between the two algorithms is how that frontier is stored. BFS uses a first-in-first-out queue, so it always expands the closest discovered node next and fans outward in rings of equal distance. DFS uses a last-in-first-out stack, usually the call stack through recursion, so it commits to one branch and follows it to a dead end before backing up.

That single choice cascades into everything else people care about: the order nodes are visited, the memory the algorithm holds at its peak, and which classes of problem each one solves without extra bookkeeping.

When is BFS the right call?

Reach for BFS when distance matters and every edge counts the same. Because BFS discovers nodes in nondecreasing order of distance from the source, the first time it reaches a node it has already found a shortest path there measured in edges. That property makes it the default for fewest-moves puzzles, word-ladder chains, and nearest-exit maze questions.

from collections import deque

def shortest_hops(graph, start, goal):
    queue = deque([(start, 0)])
    visited = {start}
    while queue:
        node, dist = queue.popleft()
        if node == goal:
            return dist
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

One detail decides whether this is correct or slow: mark a node visited when you enqueue it, not when you pop it. If you wait until pop, the same node can enter the queue through several neighbors before it is ever expanded, and the work balloons.

When should you prefer DFS?

Choose DFS when the shape of the exploration is the answer you need: a path, a cycle, or an ordering. DFS naturally tracks the branch it is currently on, which is exactly the state that cycle detection and topological sort depend on. It also tends to use less memory than BFS on wide, shallow graphs, because it only holds the current path plus the immediate frontier rather than a full level of nodes.

def has_cycle(graph):
    visiting, done = set(), set()

    def dfs(node):
        visiting.add(node)
        for nxt in graph[node]:
            if nxt in visiting:          # back edge: a cycle
                return True
            if nxt not in done and dfs(nxt):
                return True
        visiting.discard(node)
        done.add(node)
        return False

    return any(dfs(n) for n in graph if n not in done)

The three states (unseen, visiting, done) are what separate a genuine cycle from a node you simply reached along two different forward paths. A plain visited set cannot tell those apart, which is the most common bug in hand-rolled cycle detection.

Do they visit the same nodes?

From a single start node, both traversals visit exactly the set of nodes reachable from that start, just in different orders. Neither one crosses into a disconnected component on its own. If the graph might be disconnected and you need every node, wrap the traversal in a loop that starts a fresh search from each unvisited node. That outer loop is why topological sort and connected-component counting are usually written on top of DFS.

What about memory and depth limits?

On a wide graph, where each node has many neighbors, BFS can hold an enormous frontier because a single level may contain a large fraction of the graph at once. On a deep graph with long chains, recursive DFS can overflow the call stack; when depth might reach into the thousands, rewrite DFS with an explicit stack so the recursion limit is not the thing that breaks.

A quick rule captures most cases: if you fear width, lean DFS; if you fear depth or you need shortest paths, lean BFS. And remember that neither plain traversal handles weighted shortest paths. Once edges have different costs, reach for Dijkstra, or 0-1 BFS when the weights are only zero and one.

The one-line decision

Ask what the problem rewards. Fewest steps or a level-order sweep means BFS. A path, a cycle, a dependency order, or tight memory on a wide graph means DFS. Everything else, including total running time, is identical between them, so choose by the order you need, not by speed.