Graph Traversal Patterns for Interviews: BFS and DFS

Graph traversal patterns for interviews are less about memorizing BFS and DFS than about modeling a problem correctly. You identify nodes, define edges, track visited state, and then layer the required result on top: a path, component count, ordering, or cycle check.

What Graph Traversal Problems Are Really Testing#

Graph traversal problems test whether you can systematically visit related states without doing unintended work twice.

A graph contains nodes and edges. The nodes represent objects or states. The edges represent relationships or legal transitions. Your traversal starts from one or more nodes and follows those edges.

The graph may be explicit:

A -> B, C
B -> D
C -> D
D -> []

It may also be hidden inside another structure:

• A grid: each cell is a node, and neighboring cells define edges.
• A tree: each tree node is a graph node, and parent-child links are edges.
• A dependency network: tasks are nodes, and prerequisites are directed edges.
• A state space: each state is a node, and each legal operation creates an edge.
• A social network: people are nodes, and relationships are edges.

The traversal itself is usually simple. BFS uses a queue. DFS uses recursion or a stack. The harder part is identifying what the traversal must compute.

Common tasks include:

• Determine whether one node can reach another.
• Count connected components.
• Find the shortest path in an unweighted graph.
• Detect a cycle.
• Record a parent for path reconstruction.
• Process nodes after their descendants.
• Assign groups or colors.
• Explore every valid state.

Separate the mechanics from the result. “Visit all reachable nodes” is the traversal. “Count how many times you must start that traversal” is the connected components algorithm. “Return the first distance at which you reach the target” turns BFS into an unweighted shortest-path algorithm.

That separation helps you explain your solution. First define the graph. Then choose the traversal. Finally state what information you collect.

How to Recognise Graph Traversal Patterns for Interviews#

You should consider graph traversal when the prompt describes objects connected by relationships or states connected by valid moves.

Typical signals include:

• connected
• reachable
• route or path
• groups or clusters
• islands or regions
• dependencies
• prerequisites
• minimum moves
• fewest steps
• transformation sequence
• neighboring cells
• network
• cycle

The prompt does not need to use the word “graph.” Matrix traversal interview problems often present an implicit graph.

Suppose you can move up, down, left, or right through open grid cells. You can model that as:

• Each open cell (row, column) is a node.
• An edge exists between two cells when one legal move connects them.
• Blocked cells are absent from the graph.
• Boundary checks prevent transitions outside the grid.

You usually should not build a separate adjacency list for a grid. Generate neighbors when you visit a cell.

Use this recognition checklist:

1. What are the nodes?
   People, tasks, words, grid cells, positions, or complete states.

2. What are the edges?
   Relationships, dependencies, valid moves, or transformations.

3. Where does traversal begin?
   One source, several sources, or every node in an outer loop.

4. What prevents revisits?
   A visited set, a boolean matrix, a color array, or mutation of the input.

5. What output does the problem require?
   Reachability, distance, component count, ordering, path, or cycle status.

A useful follow-up is to ask whether the graph is directed. In an undirected graph, an edge works both ways. In a directed graph, A -> B does not imply B -> A. That distinction changes cycle detection, reachability, and dependency processing.

BFS vs DFS: How to Choose During an Interview#

Choose BFS when distance by number of edges matters; choose DFS when you mainly need complete exploration or descendant-first processing.

Breadth-first search uses a queue. It explores nodes in layers:

• distance zero from the source
• then distance one
• then distance two
• and so on

That gives BFS its key property: in an unweighted graph, the first time BFS reaches a node, it has found a path using the fewest edges.

Use BFS for:

• Unweighted shortest paths
• Minimum-move questions
• Level-order exploration
• Finding all nodes within a given number of steps
• Spreading processes that advance in rounds
• Multi-source distance calculations

Depth-first search follows one route as far as possible before returning. Recursive DFS uses the call stack. Iterative DFS uses an explicit stack.

Use DFS for:

• Exhaustive reachability
• Connected components
• Flood fill
• Backtracking-style state spaces
• Postorder processing
• Directed graph cycle detection
• Subtree calculations

Many BFS vs DFS interview questions do not have one mandatory choice. If the task only asks whether a target is reachable, either traversal works. If you need to mark every cell in an island, either works. Choose the version you can implement and explain cleanly.

The distinction becomes important when the problem asks for a shortest unweighted path. A plain DFS may find a path, but not necessarily the path with the fewest edges. BFS provides that guarantee because of its layer order.

Neither traversal automatically solves weighted shortest paths. Once edges have different costs, a queue-based BFS template is generally not enough.

Reusable Python Templates for BFS and DFS#

A reliable graph traversal Python template marks nodes visited when they enter the worklist, not after they leave it.

Assume graph[node] returns the node’s neighbors.

Breadth first search template#

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = {start}

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return visited

Marking neighbor before enqueueing it matters. If two nodes both point to the same unvisited neighbor, delayed marking can enqueue that neighbor twice.

Recursive depth first search template#

def dfs_recursive(graph, start):
    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return visited

The node is marked before visiting its neighbors. This prevents a cycle such as A -> B -> A from recursing forever.

Iterative depth first search template#

def dfs_iterative(graph, start):
    stack = [start]
    visited = {start}

    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return visited

You may see iterative DFS implementations that mark a node when popping it. Those can still be correct if they check for previously visited nodes, but the stack may accumulate duplicate entries. Marking on push avoids that extra work.

For an adjacency-list graph, BFS and DFS both take O(V + E) time:

• Each vertex is processed at most once.
• Each adjacency-list edge is examined at most once per stored direction.

Both use O(V) auxiliary space in the worst case. BFS stores queued nodes. Iterative DFS stores stack entries. Recursive DFS uses call-stack frames and the visited set.

For disconnected graphs, a single call from one start node is not enough. Add an outer loop:

visited = set()

for node in graph:
    if node not in visited:
        traverse(node, visited)

Each new traversal discovers one component.

Worked Example: Number of Islands#

The [LeetCode 200: Number of Islands) problem is a connected-components problem on an implicit grid graph.

Each land cell is a node. An edge connects horizontally or vertically adjacent land cells. Water cells are not part of any component.

The algorithm is:

1. Scan every grid cell.
2. When you find unvisited land, increment the island count.
3. Start a traversal from that cell.
4. Mark every reachable land cell visited.
5. Continue scanning.

Here is a complete iterative DFS solution:

class Solution:
    def numIslands(self, grid):
        if not grid or not grid[0]:
            return 0

        rows, cols = len(grid), len(grid[0])
        visited = set()
        islands = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] != "1" or (row, col) in visited:
                    continue

                islands += 1
                stack = [(row, col)]
                visited.add((row, col))

                while stack:
                    current_row, current_col = stack.pop()

                    for row_delta, col_delta in directions:
                        next_row = current_row + row_delta
                        next_col = current_col + col_delta

                        in_bounds = (
                            0 <= next_row < rows
                            and 0 <= next_col < cols
                        )

                        if (
                            in_bounds
                            and grid[next_row][next_col] == "1"
                            and (next_row, next_col) not in visited
                        ):
                            visited.add((next_row, next_col))
                            stack.append((next_row, next_col))

        return islands

Trace this grid:

1 1 0 0
0 1 0 1
1 0 0 1

The scan proceeds as follows:

• At (0, 0), you find unvisited land. Increase islands from zero to one.
• DFS visits (0, 0), (0, 1), and (1, 1). Those cells form one component.
• The scan skips those visited cells.
• At (1, 3), you find new unvisited land. Increase islands from one to two.
• DFS also reaches (2, 3).
• At (2, 0), you find another unvisited land cell. Increase islands from two to three.
• No valid land neighbor connects it to an earlier component.

The answer is three.

The scan examines every cell. The traversal may also examine each cell and its constant number of neighbors. Time complexity is O(rows × columns).

The visited set and stack can both grow with the grid. Worst-case auxiliary space is O(rows × columns).

You could mutate visited land into water instead of keeping a set. That preserves the same asymptotic bounds and can reduce separate storage, but it changes the input. State that choice before using it.

Graph Traversal Variations Worth Knowing#

Most graph traversal variations add state to the same BFS or DFS skeleton.

Multi-source BFS#

Multi-source BFS begins with several nodes in the queue. Mark every source visited and assign each distance zero before traversal starts.

Use it when you need the distance to the nearest source or when a process spreads simultaneously from several locations. The queue still explores in layers, but the first layer contains all sources.

Parent tracking#

A visited set tells you whether a node was reached. It does not reconstruct the route.

Store a parent mapping when discovering each node:

parent[neighbor] = node

After reaching the target, follow parent pointers backward and reverse the result. This adds path information without changing the traversal’s asymptotic bounds.

Bipartite coloring#

A bipartite check assigns one of two colors to each node. Every edge must connect nodes with different colors.

Here, a plain visited set is not enough. You need a mapping from node to color. Disconnected graphs also require an outer loop so that every component is checked.

Graph cycle detection#

Cycle detection needs different state depending on the graph type.

For an undirected graph, track the node’s parent. Reaching a visited neighbor is a cycle only when that neighbor is not the parent you just came from.

For a directed graph, use states such as:

• unvisited
• currently exploring
• fully processed

An edge to a currently exploring node indicates a directed cycle. A basic boolean visited set cannot distinguish that case from an edge to a completed node.

Topological traversal#

A topological ordering applies to directed acyclic graphs. You can produce one with DFS postorder or with queue-based processing of nodes whose indegree is zero.

This variation requires more than ordinary reachability. DFS needs processing states to detect cycles. The queue-based method needs an indegree count for each node.

For focused practice, use the BFS pattern hub, the DFS pattern hub, and the topological sort pattern hub.

Common Graph Traversal Mistakes#

Most traversal bugs come from incomplete coverage or incorrect visited-state handling.

Starting from only one node#

A traversal from one source covers only that source’s reachable component. If the problem concerns the whole graph, loop over every node and start a new traversal when necessary.

Marking visited too late#

In BFS, mark a node when enqueueing it. In iterative DFS, mark it when pushing it. Otherwise, several incoming edges may add duplicate work.

Forgetting visited state#

Cycles make traversal without visited tracking repeat indefinitely. Even acyclic-looking state spaces may contain reverse moves that lead back to earlier states.

Mutating input unexpectedly#

Changing grid cells can be a clean alternative to a separate visited matrix. It can also violate the caller’s expectations. Tell the interviewer whether you intend to preserve or modify the input.

Confusing values with identities#

Two nodes may contain the same value without being the same node. Use stable identifiers, coordinates, or object identity when tracking visits.

Ignoring recursion depth#

Recursive DFS is concise, but a long chain creates one call frame per node. In Python, an iterative DFS is safer when the graph may be deep. This does not make iterative DFS universally better. It removes dependence on recursion depth.

Test the following cases before you finish:

• An empty graph or grid
• One isolated node
• Several disconnected components
• A self-loop
• A cycle
• Duplicate edges
• A graph with one long chain
• A grid with one row or one column
• A grid containing only water
• A grid containing only land

These cases expose assumptions about starting points, boundaries, revisits, and component coverage.

How to Explain a Traversal Solution Aloud#

A strong explanation names the representation, traversal choice, visited state, result, and complexity in that order.

You can use this compact script:

I will model each item as a node and each valid relationship as an edge. I will use BFS because the problem asks for the fewest unweighted steps. I will mark nodes visited when I enqueue them, which prevents duplicate queue entries and handles cycles. The search stops when I reach the target or exhaust the reachable component. With an adjacency list, the time complexity is O(V + E), and the auxiliary space is O(V).

For a component problem, adjust the middle:

Either BFS or DFS can mark one complete component. I will use iterative DFS because the stack implementation is direct here. I will loop over every node, and each unvisited node starts a new component traversal.

Avoid saying BFS is faster than DFS as a general rule. On an adjacency-list graph, both have O(V + E) traversal time. Their exploration order differs, and that order determines which one fits the required result.

Finish with a concrete test walkthrough:

On an empty input, I return immediately. On one isolated node, the outer loop starts one traversal and counts one component. On a cycle, visited marking prevents repeated processing. On a disconnected graph, the outer loop starts another traversal for each remaining component.

That closing walkthrough confirms more than the happy path. It shows that your model handles boundaries, cycles, and disconnected input without changing the core algorithm.