BFS vs DFS: Choosing the Right Graph Traversal for the Job

Breadth-first search and depth-first search are two of the most important traversal patterns in computer science. They are simple on paper, but many interview mistakes happen because people know how each one works without knowing when to choose them.

The right question is not "Can I solve this with BFS or DFS?" Usually you can solve it with either. The better question is, "Which traversal makes the problem easier and less error-prone?"

BFS in One Sentence

BFS explores nodes level by level.

That makes it ideal when you care about the shortest path in an unweighted graph or the minimum number of moves, steps, or edges.

from collections import deque

def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
    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

DFS in One Sentence

DFS explores one branch as deeply as possible before backing up.

That makes it a natural fit for:

• recursion-heavy tree problems
• exhaustive search
• cycle detection
• topological sorting
• connected component discovery

def dfs(graph: dict[int, list[int]], start: int) -> list[int]:
    visited = set()
    order = []

    def traverse(node: int) -> None:
        visited.add(node)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                traverse(neighbor)

    traverse(start)
    return order

When BFS Is Better

Choose BFS when the problem asks for:

• shortest path in an unweighted graph
• minimum number of transformations
• nearest target
• level-order traversal

Classic examples:

• Word Ladder
• Rotten Oranges
• Binary tree level order traversal

When DFS Is Better

Choose DFS when you need:

• all paths
• recursive structure
• backtracking through decisions
• postorder information from children before parents

Classic examples:

• Number of Islands
• Clone Graph
• Course Schedule cycle detection
• Path Sum

Grids Are Graphs Too

A lot of "matrix" problems are actually graph traversal in disguise. Each cell is a node and its neighbors are adjacent cells.

That is why island-counting, flood fill, shortest path in a maze, and infection spread problems often reduce to BFS or DFS.

Common Mistakes

• Forgetting a visited set in general graphs
• Using DFS for shortest path when BFS gives it for free
• Marking nodes as visited too late in BFS and adding duplicates
• Mutating the graph or grid in inconsistent ways

Complexity

For a graph with V vertices and E edges:

The choice is less about asymptotic complexity and more about what information the traversal naturally gives you.

Quick Rule of Thumb

• Need the minimum number of steps? Start with BFS.
• Need to fully explore structure or recurse on children? Start with DFS.

Practice These Next

• Number of Islands
• Binary Tree Level Order Traversal
• Rotting Oranges
• Course Schedule
• Word Ladder

Once you stop treating BFS and DFS as interchangeable templates, graph problems become much easier to classify.