If you're traversing a graph that may contain cycles, what do you need to track, and what goes wrong if you don't?

technical-conceptual · Junior level · software-engineering

What the interviewer is really asking

Assesses whether the candidate understands why a visited set is mandatory on cyclic graphs, the failure mode without it, and the nuance of recursion-stack tracking for cycle detection in directed graphs.

What to say

• State the core requirement: you must track which nodes you've already visited (a set, or a boolean per node) and skip any you've seen, because unlike a tree a graph can revisit a node via a different edge.
• Name the failure without it: on a cyclic graph the traversal loops forever — A to B to A to B — or on a DAG with shared subgraphs it re-explores the same nodes exponentially, blowing up the runtime even if it eventually terminates.
• Add the directed-graph nuance: detecting a cycle in a directed graph needs more than a 'visited' set — you track nodes on the current recursion/DFS path (the gray/in-progress set), and seeing a node that's still on the active path is what proves a back edge, hence a cycle.

What to avoid

• Say a visited set isn't needed because 'you just won't go back the way you came' — a graph has many edges into a node, so you can re-enter it from a different direction.
• Conflate detecting a cycle with simply having visited a node before: in a directed graph, revisiting an already-finished node is fine; it's revisiting a node still on the current path that signals a cycle.
• Forget that without a visited set even a finite DAG with diamond-shaped sharing re-traverses subgraphs and can become exponential.

Example answers

Strong: I track a visited set and skip any node already in it, because a graph — unlike a tree — can reach the same node through multiple edges. Without it, a cycle like A-B-A makes the traversal loop forever, and even an acyclic graph with shared subpaths gets re-explored, which can blow up to exponential time. So the visited set is what guarantees each node and edge is processed once, keeping it O(V + E).

Weak: As long as I don't immediately go back to the node I came from, I won't get stuck in a loop.