Graph Traversal: Complete Guide with BFS and DFS Examples

Graph traversal is the skill you build every graph solution on. Before you can find a shortest path, detect a cycle, or check whether two nodes are connected, you have to visit the nodes in some order. BFS and DFS are the two standard orders, and almost every graph interview problem is one of them with a small twist attached.

Definition: graph traversal visits every node and edge of a graph in a systematic order. Breadth-First Search (BFS) visits nodes in order of their distance from the start. Depth-First Search (DFS) follows one path as far as it goes before backtracking and trying the next one.

Real-World Analogy

Rumors spread the way BFS does. One person tells their direct friends, and each of those friends tells their own direct friends. Nobody skips ahead in the chain. If you are the third person to hear the rumor, it reached you through exactly two intermediaries, and it could not have reached you faster. That is why BFS finds shortest paths in unweighted graphs. Every layer of the search is one more link in the chain, and the first time a node appears, it appeared by the shortest route.

DFS works differently. Picture exploring a cave system with one flashlight and a single rope. You walk down the first tunnel you find until it dead-ends. Then you come back to the last fork and take the next tunnel. You never see the whole map at once, but you do reach every dead end. Problems that ask you to explore every option exhaustively are DFS problems.

Visual Explanation

Both searches are built from the same skeleton, made of a container, a visited check, and a loop. BFS uses a queue, so nodes are processed in the order they were discovered. DFS uses a stack, so the most recently discovered node is processed first. Recursion gives DFS its stack for free, since the call stack is a stack.

    graph TD
    S["Enqueue start, mark visited"] --> C{"Queue empty?"}
    C -->|No| D["Dequeue node"]
    D --> E["For each unvisited neighbor: mark and enqueue"]
    E --> C
    C -->|Yes| F["All reachable nodes visited in layer order"]
  

    graph TD
    S["Push start, mark visited"] --> C{"Stack empty?"}
    C -->|No| D["Pop node"]
    D --> E["Push unvisited neighbors, mark them"]
    E --> C
    C -->|Yes| F["All reachable nodes visited, path by path"]
  

The two diagrams differ only in the container. Everything else, the visited marking and the neighbor loop, is the same code. That is the part people forget in an interview. If you skip the visited check, a cyclic graph puts the search into an infinite loop, and the interviewer watches you realize it.

A concrete trace makes the layers visible. Take a small graph where A connects to B and D, B connects to C and D, and D connects to C. Starting from A, BFS visits A first, then B and D as layer one, then C as layer two. C is reachable from both B and D, but it is enqueued only once, because B marks it before D is processed. DFS from the same start visits A, then B, then C, then backtracks to B, then D. The neighbor order is arbitrary, which is why DFS order is not unique. The layers of BFS are fixed; only the order inside a layer varies.

When to Use This Pattern

Use BFS when:

• The graph is unweighted and you need the shortest path or the minimum number of steps between two nodes. BFS is guaranteed to find it, because the first time a node is discovered, it was reached by the fewest edges.
• The problem counts layers or rounds of spread, like the number of minutes until a process covers an area.
• Several starting points act at the same time. Put every source in the queue before the first iteration, and one BFS handles all of them together.
• You need to process everything at distance k before anything at distance k + 1.

Use DFS when:

• The problem asks you to enumerate all possibilities or all paths, such as every way to fill a board.
• The question is about connectivity: count connected components, flood fill a region, or check whether two nodes are reachable from each other.
• You can carry state down a path, like a running path or a set of used elements, and you want to undo it when you backtrack.
• You need a topological order of a directed acyclic graph or a post-order traversal. The topological sort page builds on this.

One shared case covers both. When the input is a 2D grid where adjacent cells are neighbors, the traversal is plain BFS or DFS, and the only added work is the bounds check on each move. The matrix guide covers grid mechanics; the search itself is this pattern.

Complexity Analysis

Where V is the number of vertices and E is the number of edges:

The time is

Common Mistakes

Marking nodes visited at dequeue time instead of enqueue time. If a node is marked only when it is processed, every neighbor that discovers it enqueues it again. In a dense graph the same node can sit in the queue many times, and the queue grows in proportion to the edges. Mark a node the moment you put it in the container. The first node to discover it is also the one that found the shortest path to it, so marking early changes nothing about the results.

To catch this during practice, count the nodes in your result against the graph. If any node appears twice, the marking is in the wrong place.

Recursive DFS on a graph that is too deep. The call stack is not infinite. A graph shaped like a long chain overflows it well before a few thousand nodes. If the constraints are large, or the interviewer mentions hundreds of thousands of nodes, switch to iterative DFS with an explicit stack. The logic is identical, only the stack is yours instead of the runtime’s.

Running one traversal and assuming the whole graph is visited. A graph can be disconnected. One BFS from a single start only reaches that start’s component, and the rest of the graph is untouched. Problems that want every node need a loop that starts a new search from each unvisited node. Each new start counts as one more connected component, which is itself often the answer.

Using DFS where the question asks for the fewest steps. DFS finds a path, not the shortest path. If the problem wants the minimum number of moves, edges, or operations, BFS is the tool, because it explores by distance layers and stops the first time the target is discovered. DFS would have to try every path to find the best one, which is exponential in the worst case. When you hear “minimum”, reach for a queue.

Related Patterns

• Shortest Path . BFS is the unweighted case of shortest path. When edges carry weights, Dijkstra’s algorithm replaces the queue with a priority queue and visits nodes in order of distance.
• Union Find . Union Find answers connectivity questions, like whether two nodes are in the same component, often faster than a traversal. It cannot produce paths or orderings, so the two approaches complement each other.
• Topological Sort . Topological sort is BFS or DFS applied to a directed acyclic graph, with an extra step that emits nodes in dependency order. It shares the traversal skeleton and adds a cycle check.

Next Steps

Once BFS and DFS make sense conceptually, the next step is making the code automatic. Check out the code templates for implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.