DSA · Patterns, not puzzles
How do you detect a cycle in a graph?
Short answer
In a directed graph, DFS with a recursion-path set detects a back edge. In an undirected graph, DFS with a parent pointer or union-find detects an edge to an already visited node that is not the parent.
The definition differs by graph type. A directed cycle is a path that returns to a node while following edge direction. In an undirected graph, the edge you came from is not a cycle, so you must exclude the parent. Mixing the two rules produces false positives.
function hasDirectedCycle(graph) {
const visiting = new Set();
const visited = new Set();
function visit(node) {
if (visiting.has(node)) return true;
if (visited.has(node)) return false;
visiting.add(node);
for (const next of graph.get(node) || []) {
if (visit(next)) return true;
}
visiting.delete(node);
visited.add(node);
return false;
}
for (const node of graph.keys()) {
if (visit(node)) return true;
}
return false;
}Undirected alternatives
- DFS with a parent parameter ignores the edge you arrived on
- Union-find detects a cycle when an edge connects two nodes already in the same set
- Kahn's algorithm detects a directed cycle when it cannot process all nodes
- For a functional graph, Floyd's tortoise and hare detects a cycle with O(1) space
- Self-loops and parallel edges need explicit handling
function hasUndirectedCycle(graph, node, parent, visited) {
visited.add(node);
for (const next of graph.get(node) || []) {
if (!visited.has(next)) {
if (hasUndirectedCycle(graph, next, node, visited)) return true;
} else if (next !== parent) {
return true;
}
}
return false;
}Follow-ups you should expect
Interviewers use these to check whether the first answer was understanding or memorisation.
- 1How does directed cycle detection differ from undirected?
- 2How does union-find detect an undirected cycle?
- 3What is Floyd's cycle detection algorithm?
- 4Why must a node stay in the visiting set during DFS?
Say it in the interview
For a directed graph I run DFS and keep a set of nodes on the current recursion path, so reaching a node already in that set means I found a cycle. For an undirected graph I track the parent so the edge I came from is not counted. Union-find and Kahn's algorithm are alternatives, but the key detail is not marking a node fully visited until its subtree is complete.
Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.
Related questions
Reading is step one
Now say it out loud.
Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.