BFS and DFS: Walking a Graph

Search algorithms are what allow you to traverse a graph and make sense of what it looks like. In a real problem it can help you answer questions like, "can I reach node X from Y?" and "which nodes are in the same connected clump as this one? Is there a cycle?"

Basic Idea

Take the node that has been waiting longest, and the collection behaves as a queue. You finish everything one step from the start before you look at anything two steps away, and the search spreads outward in rings. This is breadth-first search.

Take the node you added most recently, and the collection behaves as a stack. You charge as deep as you can down a single path, and only when you run out of new ground do you back up to the most recent turning you skipped. That is depth-first search.

| In code the difference is shift() against pop().

Try it out first

Below is one graph, wired the same way for both runs. Neighbors are always tried in alphabetical order, so the run is reproducible and every step matches the caption underneath it. Try visualizing what the next step is and figure out the difference between BFS and DFS.

From here, you've probably noticed that the difference between BFS and DFS in words is that BFS checks branch by branch and DFS checks nodes in order of how far it is from the root.

More Examples

Switch between the two modes and click a different start node. The panel shows the queue or stack contents as they change, which is the part worth watching: the same graph, the same neighbors, and completely different shapes of exploration.

Why BFS gets shortest paths

| when BFS first reaches a node, the number of steps it took is minimal

Put simply, BFS checks by distance starting with the closest. It then follows that the first time it reaches a certain node, that's the least distance because you checked each possibility from least distance to greatest.

Since nodes come out in non-decreasing order of distance, the first time you meet a node is via the shortest route to it. In summary, BFS finds all possibilities starting with the shortest ones (unweighted).

function shortestPathLengths(graph, start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    for (const next of graph.neighbors(node)) {
      if (dist.has(next)) continue;
      dist.set(next, dist.get(node) + 1);   // one more layer out
      queue.push(next);
    }
  }

  return dist;
}

DFS gives you no such promise. In the trace above it reached D at depth 4 down its walk, when D is two steps from A. If you need shortest paths on an unweighted graph, use BFS. If the edges have costs, neither of these is enough and you want Dijkstra, which is the next page.

What depth-first search is better at

DFS has a property BFS lacks: at any moment, the chain of calls you are inside is the current path from the source. That makes it the natural fit whenever the question is about paths and structure rather than distance.

This makes it useful for something like detecting cycles. If DFS ever finds an edge back to a node that is still open, meaning you are still inside its call, you have found a cycle, and the nodes on the current call stack are the cycle. Topological sorting falls out of the order in which DFS finishes nodes. Tarjan's algorithm for strongly connected components is DFS with two extra numbers per node.

The recursive version

DFS is usually written recursively, because the language's own call stack already does the bookkeeping the explicit stack was doing, and the resulting code reads more clearly since there is no stack variable left to manage by hand.

function dfs(graph, node, seen = new Set()) {
  seen.add(node);
  for (const next of graph.neighbors(node)) {
    if (!seen.has(next)) dfs(graph, next, seen);
  }
  return seen;
}

The trap is that a real call stack has a size limit. On a graph shaped like a long chain of a hundred thousand nodes, the recursion goes a hundred thousand frames deep and the program dies with a stack overflow. The iterative version with an explicit array handles the same graph without complaint. On competitive programming sites this is a common and confusing source of runtime errors, since the logic is perfectly correct.

There is also a small difference in visit order between the two. The explicit stack pushes all neighbors and then pops the last one, so it explores the final neighbor first. The recursive version dives into the first neighbor immediately. Both are valid depth-first traversals, and if a problem depends on exactly which one you used, the problem statement usually pins the order down for you.

What it costs

The analysis is the same for both, which is another sign of how similar they are.

Every node enters the collection at most once, because the seen check blocks it after that, so the outer loop runs at most V times. Inside, you scan a node's neighbor list exactly once, and across the whole run every edge is looked at once from each end. Adding those together gives O(V + E) time.

Memory is O(V) for the seen set plus whatever the queue or stack is holding. The worst case differs in a way that occasionally matters: BFS on a wide graph can hold an entire layer at once, which on a broad graph is most of the nodes. DFS holds one root-to-leaf path, which on a deep graph is also most of the nodes. Neither is universally lighter, and it depends on the shape in front of you.

Common Mistakes

There is one bug that catches nearly every person learning BFS, and it is worth meeting on purpose rather than at two in the morning.

Marking nodes as seen when you take them out, instead of when you put them in: If you only mark on removal, a node that is adjacent to three already-processed nodes can be added to the queue three separate times before it is dequeued.

from collections import deque

def bfs_bad(graph, start):
    queue = deque([start])
    visited = set()
    push_count = 0  # Tracks queue entries
    
    while queue:
        current = queue.popleft()
        
        # BAD: Marking as visited ONLY when taking it out
        if current in visited:
            continue
        visited.add(current)
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                queue.append(neighbor)
                push_count += 1
                
    return push_count

Assuming one traversal reaches everything. A graph can come in several disconnected pieces. One traversal only covers the piece containing your start node. To touch every node, loop over all of them and start a fresh traversal from any that are still unseen. The number of times you have to do that is the number of connected components, which is a free and often useful answer.

Forgetting that an undirected edge is two directed edges. If you build your adjacency list by hand, an edge between A and B has to appear in both lists.

2 in 1

Since the only difference is which end you take from, it is honest to write them as one function. Reading it this way makes the relationship hard to forget.

function traverse(graph, start, mode) {
  const seen = new Set([start]);     // mark on the way IN, not on the way out
  const pending = [start];
  const order = [];

  while (pending.length > 0) {
    const node = mode === "bfs" ? pending.shift() : pending.pop(); // only change
    order.push(node);

    for (const next of graph.neighbors(node)) {
      if (seen.has(next)) continue;
      seen.add(next);
      pending.push(next);
    }
  }

  return order;
}

Check yourself