Graph Traversals: BFS vs. DFS

Graphs show up everywhere once you start seeing them.

Social networks, route maps, dependency trees, build systems, recommendation engines. They all boil down to nodes and relationships.

Once you have a graph, one of the first questions is simple: how do I walk through it?

Two of the basic answers are breadth-first search and depth-first search. They are both graph traversals. They are both usually O(V + E). And they are not interchangeable once the traversal order actually matters.

BFS: explore outward layer by layer

Breadth-first search visits nodes by distance from the starting point.

That makes it useful when you care about the shortest path in an unweighted graph or when you want to answer questions like "What is reachable in one step? Two steps? Three?"

function bfsIterative<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];
  const queue: T[] = [start];
 
  while (queue.length > 0) {
    const node = queue.shift()!;
    if (visited.includes(node)) continue;
 
    visited.push(node);
    queue.push(...graph.getNeighbors(node));
  }
 
  return visited;
}

If you are searching a social graph for the fewest introductions between two people, BFS is usually what you want. It reaches the closest options first.

DFS: follow one path deeply before backing up

Depth-first search does the opposite. It picks a branch and keeps going until it hits a dead end, then backtracks.

That is useful when you care more about fully exploring structure than staying near the starting point.

function dfsRecursive<T>(graph: Graph<T>, start: T): T[] {
  const visited: T[] = [];
 
  function visit(node: T) {
    if (visited.includes(node)) return;
 
    visited.push(node);
    graph.getNeighbors(node).forEach(visit);
  }
 
  visit(start);
 
  return visited;
}

That makes DFS a natural fit for problems like:

• walking nested dependency structures
• finding connected components
• checking reachability
• producing traversal orders that feed other algorithms

The practical difference

The simplest way to remember the difference is this:

• BFS answers "What is nearest?"
• DFS answers "What is connected if I keep following this path?"

Both visit nodes.

But the order changes the meaning of the result.

That is the part people often skip when they first learn these algorithms. They memorize queue versus stack and miss the real question: what does the traversal order buy me here?

Recursive or iterative?

Both algorithms can be written recursively or iteratively. The real control structure underneath is:

• BFS wants a queue
• DFS wants a stack, whether explicit or implicit through recursion

In practice, iterative versions are often easier to control for large graphs, especially when recursion depth becomes a risk.

Recursive versions can still be great for learning and for smaller, clearer implementations.

Why this matters outside interview questions

The value in learning BFS and DFS is not the code itself. It is the intuition that traversal order changes what is easy to answer.

Once that clicks, a lot of problems get easier to model.

You stop asking "Which algorithm am I supposed to use?" and start asking the better question: "What kind of walk over this structure matches the answer I need?"