Mastering Graph Traversal Algorithms for Interviews

Graph traversal is one of the most reliably tested areas in coding interviews. From connected components and shortest paths to Clone Graph and Course Schedule, interviewers reach for graph problems because they reveal how you model connected data and how systematically you explore a search space. If you are preparing for a graph algorithms interview, this guide covers the core toolkit: representations, BFS and DFS, cycle detection, shortest paths, topological sort, connected components, and the classic problems that map to these patterns.

Quick answer: The two foundational graph traversal algorithms are BFS (Breadth-First Search) and DFS (Depth-First Search). BFS explores nodes level by level using a queue, making it the right choice for shortest paths in unweighted graphs and level-order problems. DFS dives deep along one path before backtracking, using a stack (explicit or the call stack), and is better for cycle detection, topological sort, and path-existence checks. Represent your graph as an adjacency list in most cases. Almost every graph question fits one of five patterns: reachability, shortest path, cycle detection, topological ordering, or connected components. Identify the pattern before you write any code.

How to Represent a Graph in Code

Before you traverse anything, you need to store the graph. The two standard representations are the adjacency list and the adjacency matrix.

Adjacency list: Each node maps to a list of its neighbours. A dictionary (or array of lists) covers most interview scenarios cleanly.

# Python adjacency list
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1]
}

Space complexity is O(V + E), where V is the number of vertices and E is the number of edges. For sparse graphs (the kind most interview problems give you), this is far more memory-efficient than a matrix.

Adjacency matrix: A 2D array where matrix[i][j] = 1 (or the edge weight) if an edge exists. Space is O(V^2). Use this when the graph is dense, or when you need O(1) edge-existence lookups. In typical interview problems, those conditions are rare.

Implicit graphs: Many problems do not hand you an explicit edge list. Number of Islands gives you a 2D grid; the graph is every cell, and edges connect adjacent land cells. Clone Graph gives you a node reference; you discover neighbours as you traverse. Part of your first move on any graph problem should be mentally sketching the adjacency structure.

Always clarify two things before you code: is the graph directed or undirected, and can it contain cycles? Those two properties determine which algorithm variant applies.

BFS Explained: Level-by-Level Exploration

Breadth-First Search visits all neighbours of a node before moving to their neighbours. You implement it with a queue and a visited set.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

Time complexity: O(V + E). Every vertex and every edge is processed at most once. Space complexity: O(V) for the visited set and queue.

When to reach for BFS:

• Shortest path in an unweighted graph or a grid where all moves cost 1. BFS guarantees you find the minimum-hop path first because you explore strictly by distance.
• Level-order problems: printing nodes by depth, finding all nodes at distance k from a source.
• Multi-source BFS: seed the queue with several starting nodes simultaneously. This is the key trick for problems like "0/1 matrix" (find distance from every cell to the nearest 0) or "rotting oranges" (spread from all rotten cells at once).

BFS is the safer choice when the graph can be very deep. Recursive DFS on a deep graph risks a stack overflow; BFS does not.

DFS Explained: Iterative vs Recursive

Depth-First Search follows one path as far as it goes, then backtracks and tries another. You can implement it recursively (the call stack manages state) or iteratively (you manage an explicit stack).

Recursive DFS:

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

Iterative DFS:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                stack.append(neighbour)

Iterative DFS using a stack does not always visit nodes in the same order as recursive DFS because you push neighbours in the same order and pop in reverse. For reachability and connected-component problems this does not matter. For topological sort you need the post-order variant from recursive DFS (discussed below).

When to reach for DFS:

• Checking whether a path exists between two nodes.
• Cycle detection in directed and undirected graphs.
• Topological sort.
• Finding all paths from source to target (backtracking).
• Identifying connected components.

Cycle Detection in Directed and Undirected Graphs

Interviewers ask about cycle detection in two different contexts, and the technique differs between them.

Undirected graph: Track visited nodes and the parent of each node. If during BFS or DFS you encounter a neighbour that is already visited and is not the parent of the current node, you have found a back edge and a cycle.

Directed graph: Use three-state coloring. A node is white (unvisited), grey (currently on the DFS call stack), or black (fully processed). If you encounter a grey node during DFS, you have found a back edge, which means a cycle exists.

def has_cycle_directed(graph, node, visiting, visited):
    visiting.add(node)
    for neighbour in graph.get(node, []):
        if neighbour in visiting:
            return True  # back edge: cycle found
        if neighbour not in visited:
            if has_cycle_directed(graph, neighbour, visiting, visited):
                return True
    visiting.remove(node)
    visited.add(node)
    return False

The distinction matters in interviews. Saying "I will track visited nodes" without mentioning parent tracking (undirected) or three-color state (directed) signals a surface-level understanding. An interviewer will probe this. Know both variants cold.

Shortest Paths: BFS for Unweighted Graphs, Dijkstra for Weighted

If every edge has the same cost (or no cost), BFS finds the shortest path in O(V + E) time. Enqueue each node with its distance from the source; the first time you reach the destination is the shortest path.

For weighted graphs with non-negative edge weights, Dijkstra's algorithm is the standard. It uses a min-heap (priority queue) and relaxes edges greedily: always expand the cheapest unvisited node next. Time complexity is O((V + E) log V) with a binary heap. In Python, heapq gives you this.

A few practical notes for interviews:

• Dijkstra does not work with negative edge weights. For that case, Bellman-Ford (O(VE)) is the fallback. If negative cycles are possible, Bellman-Ford can detect them.
• In grid problems where cells have different movement costs, Dijkstra on the implicit grid graph is often cleaner than a modified BFS with extra state.
• "Shortest path with only 0-weight and 1-weight edges" is a known interview variant designed to test whether you reach for Dijkstra reflexively. The correct answer is a 0-1 BFS using a deque: push weight-0 neighbours to the front, weight-1 neighbours to the back. It runs in O(V + E).

Be prepared to justify your choice of algorithm before coding. "I will use BFS because all edges have equal weight, so BFS finds the shortest path in O(V + E) without a heap" is a complete answer. Just saying "BFS" is not.

Topological Sort and Connected Components

Topological sort orders the nodes of a directed acyclic graph (DAG) such that for every directed edge from u to v, u appears before v in the ordering. Two implementations come up in interviews.

Kahn's algorithm (BFS-based): Compute in-degrees for all nodes. Enqueue all nodes with in-degree 0. Pop a node, add it to the result, decrement the in-degree of its neighbours, and enqueue any neighbour whose in-degree drops to 0. If all nodes are processed, the result is a valid topological order. If the output is shorter than the total node count, the graph has a cycle.

DFS-based: Run DFS on each unvisited node. When a node's DFS call finishes (all its descendants are processed), push it onto a stack. The stack reversed gives the topological order.

Kahn's algorithm is often easier to reason about in an interview because cycle detection is built in as a side effect of the node count check.

Connected components in an undirected graph are maximal sets of nodes where every pair is mutually reachable. The algorithm: iterate through all nodes; for each unvisited node, run BFS or DFS from it, mark everything reachable as part of the same component, and increment the component count. Union-Find (Disjoint Set Union) is an alternative that handles dynamic connectivity (edges added one at a time) more efficiently, with near-O(1) amortised operations.

Mapping Classic Interview Problems to Traversal Patterns

Knowing the algorithms is half the job. The other half is recognising which pattern applies the moment you read the problem.

Number of Islands (LeetCode 200): Count distinct islands in a grid of '1's and '0's. Pattern: connected components. Iterate every cell; when you find an unvisited '1', run DFS or BFS to mark the entire island as visited and increment your counter. The grid is an implicit graph; edges connect adjacent land cells in four directions.

Course Schedule (LeetCode 207): Given n courses and prerequisite pairs, decide whether you can complete all courses. Pattern: cycle detection in a directed graph. Build an adjacency list from the prerequisite pairs, then run DFS with three-color state, or run Kahn's algorithm. A cycle means the schedule is impossible.

Clone Graph (LeetCode 133): Given a reference to a node in a connected undirected graph, return a deep copy of the entire graph. Pattern: graph traversal with memoisation. Use a hashmap from original node to cloned node. When you visit a node, create its clone if not already created, then recurse or iterate over its neighbours. The hashmap prevents revisiting and serves as your cloned-node registry.

Word Ladder and minimum-transformation problems: Pattern: BFS for shortest path. Model each word as a node, with edges to words differing by exactly one character. BFS from the start word finds the minimum number of transformations to reach the target.

General approach before coding any graph problem: state four things aloud. Is the graph directed or undirected? Can it contain cycles? Is it connected or might it have isolated components? What am I computing (a count, a path, an ordering, a distance)? Those four questions narrow the right algorithm in under a minute and signal structured thinking to the interviewer.

Frequently Asked Questions on Graph Traversal Interviews

What is the difference between BFS and DFS for a graph traversal interview? BFS explores nodes by distance using a queue and guarantees the shortest number of hops in an unweighted graph. DFS explores deep along one branch before backtracking, using a stack (explicit or the call stack). Both run in O(V + E) time. BFS suits shortest-path and level-order questions; DFS suits cycle detection, topological sort, and existence-of-path problems. Neither is universally better; choose based on what the problem is asking.

When should I use an adjacency list instead of an adjacency matrix? Use an adjacency list by default. It uses O(V + E) space, and iterating over a node's neighbours takes O(degree) time. Use an adjacency matrix when the graph is dense (number of edges close to V^2) or when you need O(1) edge-existence checks. In most coding interview problems, the graph is sparse and an adjacency list is the right choice.

How do I detect a cycle in a directed graph? Use DFS with three states: unvisited, currently in the active call stack (grey), and fully processed (black). If during DFS you reach a node that is currently in the call stack, you have found a back edge and a cycle. Alternatively, apply Kahn's algorithm for topological sort: if the resulting order contains fewer nodes than the graph has, a cycle prevented some nodes from being processed.

Can BFS be used for cycle detection? Yes, though it is less common. In an undirected graph, track each node's parent during BFS. If you reach a visited node that is not the current node's parent, a cycle exists. For directed graphs, use Kahn's algorithm: a completed topological sort with a shorter-than-expected output indicates a cycle.

What is topological sort and when does it appear in interviews? Topological sort produces a linear ordering of nodes in a DAG such that every directed edge from u to v places u before v. It appears in course scheduling, build-system dependency ordering, task sequencing, and compilation-order problems. It is only possible on directed acyclic graphs; if the graph has a cycle, no valid topological order exists, which is itself a useful detection signal.

How do I handle disconnected graphs in BFS or DFS? Wrap your traversal in a loop over all nodes. For each node that has not yet been visited, start a new BFS or DFS from it. This ensures every connected component is covered. Forgetting this loop is one of the most common bugs in connected-component counting and topological sort implementations, and interviewers look for it.

Practising Graph Traversal Out Loud with Rehurz

Solving graph problems on paper or a judge platform is useful, but interviews add a layer most practice environments skip: you have to defend your algorithm choice out loud, under live questioning, before you write a single line. Why BFS and not DFS here? What if the graph has a cycle? Why is your visited set initialised outside the loop? These questions arrive mid-explanation on a real call, not after you finish.

Rehurz coding rounds are designed around exactly this gap. You pick a problem, explain your approach aloud, and get cross-questioned on complexity, edge cases, and tradeoffs before you write any code. The session probes your reasoning in real time, the way a sharp technical interviewer would. After you write your solution, the scorecard weights your reasoning alongside your code, not just whether tests pass. See how it works to understand the full round structure.

Your first coding round is free, no card required. If graph traversal is a weak spot, that is a low-cost way to find exactly where your explanation breaks down under pressure.

Keep Going

Graph traversal is a learnable, pattern-driven skill. Once you can state the difference between BFS and DFS, recognise the five core patterns on sight, and map a new problem to the right algorithm before opening your editor, you are well-positioned for the graph algorithms interview questions that appear at most technical levels. Consistent practice under questioning, not just isolated problem-solving, is what turns algorithm knowledge into confident, real-time performance.