Graph Traversal Algorithms: BFS, DFS, and How to Choose

Most graph problems reduce to one question: how do you visit every node without getting lost, stuck in a cycle, or doing exponential work? That is what graph traversal algorithms answer. Breadth-first search and depth-first search are the two engines underneath almost every graph problem you will meet in an interview or in production, from finding the shortest route on a map to detecting a deadlock in a scheduler.

This guide compares the core graph traversal algorithms side by side: how they work, what they cost, and the decision rules that tell you which one to reach for. If you have ever picked BFS when DFS was the cleaner choice (or watched a recursive traversal blow the stack), the goal here is to make that choice deterministic.

What graph traversal actually means

A graph is a set of nodes connected by edges. Traversal is the process of starting at one node and systematically visiting others by following edges. The two things that make graph traversal harder than walking a tree are cycles and multiple paths. A tree has exactly one path between any two nodes and no cycles, so you never revisit anything. A general graph can loop back on itself, so every traversal algorithm needs a visited set to avoid infinite work.

Both breadth-first search and depth-first search visit every reachable node exactly once. The difference is the order in which they do it, and that order is what makes each one suited to different problems.

Breadth-first search: level by level

Breadth-first search explores the graph in rings. It visits the start node, then all of its neighbors, then all of their neighbors, and so on. It uses a queue to remember which nodes to visit next, which enforces first-in, first-out order and keeps the traversal expanding outward evenly.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

The property that makes BFS special: on an unweighted graph, the first time you reach a node is always along a shortest path measured in number of edges. That single guarantee is why BFS is the default tool for shortest-path questions, level-order problems, and anything where closest first matters.

Depth-first search: follow one path to the end

Depth-first search does the opposite. It picks a neighbor, follows that branch as far as it can go, and only backtracks when it hits a dead end. It uses a stack, either explicitly or through the call stack of a recursive function.

def dfs(graph, start, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(start)
    order.append(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)
    return order

DFS is the natural fit whenever the structure of a path matters more than its length: detecting cycles, producing a topological ordering, finding connected components, or exploring every possibility in a backtracking search. Its recursive form is short and readable, which is a real advantage under interview pressure.

Comparing the two algorithms

Both algorithms share the same asymptotic cost, but they trade off memory and behavior in ways that decide which one you want. The diagram below shows how each one visits the same graph in a different order.

• Data structure: BFS uses a queue (FIFO); DFS uses a stack or recursion (LIFO).
• Time complexity: both run in O(V + E).
• Space complexity: BFS uses O(V) up to the widest level; DFS uses O(V) up to the deepest path.
• Shortest path on unweighted graphs: BFS yes, DFS no.
• Natural fit: BFS for levels and nearest-first; DFS for cycles, ordering, and backtracking.
• Risk on huge inputs: a wide BFS frontier eats memory; deep DFS recursion overflows the stack.

Here V is the number of vertices and E the number of edges. Both traversals touch every node and every edge once, so both run in linear time relative to the size of the graph. The memory story is where they diverge. BFS holds an entire level in the queue at once, so a wide, bushy graph can make its frontier enormous. DFS holds a single path, so a long, chain-like graph can push recursion past the stack limit. On deep graphs, an iterative DFS with an explicit stack sidesteps that risk.

The variants that show up most often

Plain BFS and DFS are the foundation, but real problems usually call for a small twist on one of them. Recognizing the variant is half the battle.

Multi-source BFS starts the queue with several nodes at once instead of one, which computes the shortest distance from the nearest of many origins in a single pass. It is the right tool for problems like how far is every cell from the closest gate. We cover the stateful and bidirectional forms in depth in our guide to advanced BFS patterns.

Grid traversal is graph traversal in disguise: each cell is a node and adjacent cells are neighbors. Flood fill, island counting, and shortest-path-in-a-maze problems are all BFS or DFS over an implicit grid graph, as we break down in matrix problems in disguise.

When edges carry weights, plain BFS no longer finds the shortest path, because fewest edges and lowest cost stop agreeing. That is where Dijkstra's algorithm and, for a threshold twist, BFS combined with binary search take over.

A decision framework you can apply under pressure

When you see a graph problem, work through four questions in order.

1. Is the graph weighted? If yes, BFS and DFS alone will not give shortest paths; you need Dijkstra, Bellman-Ford, or a specialized approach. If no, continue.
2. Do you need the shortest path or the nearest something? If yes, use BFS and rely on its level-order guarantee. Record the distance as you enqueue each node.
3. Do you need ordering, cycle detection, or exhaustive exploration? If yes, use DFS. Track discovery and finish times if you need topological order or cycle classification.
4. Is the graph pathologically deep or wide? A very deep graph argues for iterative DFS to avoid stack overflow; a very wide graph may make BFS memory-heavy, where DFS or iterative deepening can help.

This ladder resolves the large majority of traversal questions without guesswork. For the deeper trade-off between traversal and dynamic programming as ways to explore a search space, see our comparison of BFS, DFS, and DP.

Where traversal meets real systems

These algorithms are not only interview material. Package managers run topological sort (a DFS variant) to order installs. Build systems use the same idea to schedule compilation. Web crawlers are BFS over the link graph. Garbage collectors trace reachable objects with DFS. Social networks compute degrees of separation with BFS. Once you see the queue-versus-stack distinction, you start noticing it everywhere in production code, not just in coding challenges.

Practice with intent

The fastest way to internalize graph traversal algorithms is deliberate practice on problems that force the choice, then reviewing why one algorithm was cleaner than the other. Levelop's interactive system design and coding-pattern lessons at levelop.dev walk through these traversals on real problems, and our full library of pattern breakdowns lives on the Levelop blog. Pattern recognition, not memorization, is what turns a hard graph question into a routine one.

References

Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (MIT Press), chapters on elementary graph algorithms.

CP-Algorithms: Breadth-first search

CP-Algorithms: Depth-first search

Wikipedia: Graph traversal