How to detect cycle in a graph

How do you detect cycle in graph traversal? The answer depends on whether the graph is directed or undirected, and most explanations gloss over why that distinction matters. It's not a technicality. Use the wrong method on the wrong graph type and you'll get false positives or miss real cycles entirely.

What cycle detection actually solves

A cycle is a path that starts and ends at the same node. In undirected graphs, DFS flags one when it reaches an already-visited node that isn't the direct parent. In directed graphs, DFS uses three colors to track node states, and a back edge to a grey node confirms a cycle.

That definition sounds clean, but things get messier in practice. "Already visited" means different things depending on graph type.

In an undirected graph, every edge goes both ways. If node A connects to node B, then B also connects to A. So when you run DFS from A and visit B, B's neighbor list includes A. If you just check "have I visited this neighbor before?" you'll immediately flag A as a cycle. But you literally just walked across that edge. That's not a cycle.

In a directed graph, edges have direction. A to B doesn't imply B to A, so the problem flips. You can visit a node, finish exploring all its descendants, move on to a different branch, and then hit that node again through a completely separate path. That's also not a cycle, just two paths that happen to converge on the same node.

These two situations need different detection methods. Mixing them up is the single most common mistake in cycle detection code.

The practical applications are concrete. Build systems catch circular imports. Operating systems catch circular waits that cause deadlock. Course prerequisite validators catch circular requirements. In every case, a cycle means the process is stuck and can't make forward progress.

DFS cycle detection in undirected graphs

The core idea is simple: run DFS, and for every neighbor you're about to visit, check two things. Is it already in the visited set, and is it not the node you just came from?

That parent check is the whole game. Without it, every single edge in an undirected graph looks like a cycle because adjacency is bidirectional.

Consider five nodes connected as A-B-C-D-B (forming a cycle through B-C-D) with A-E as a separate branch that has no cycle.

Walk through this on the example. You start DFS from A with parent=None and move to B (parent=A). From B, neighbors are A, C, D. You skip A because it's the parent, then go to C (parent=B). C's neighbors are B and D, so you skip B as the parent and move to D (parent=C). D's neighbors are B and C. You skip C as the parent and check B, which is already visited but isn't the parent. That confirms a cycle.

The parent parameter does all the heavy lifting. Remove it and the algorithm reports a cycle in every connected graph with more than one edge.

One thing worth noting: this handles disconnected graphs correctly only if you iterate over all nodes and start a new DFS from any unvisited node. A single DFS call from one starting node only covers its connected component.

DFS cycle detection in directed graphs

Parent tracking doesn't work here. In a directed graph, there's no "parent" in the undirected sense. Edge direction means you can arrive at a node through multiple independent paths, and that's perfectly normal. The real question isn't "did I visit this node before?" but "is this node currently in my call stack?"

That distinction requires three states instead of two. The standard algorithm assigns each node a color.

A cycle exists when DFS encounters a grey node. Grey means "I started exploring this node but haven't finished yet," so reaching it again means there's a path from this node back to itself.

A black node is totally fine. You've already explored everything reachable from it and you're reaching it through a different path, so there's no cycle.

Trace this on a directed graph with edges A to B, B to C, C to D, D to B, A to E.

You start from A (color A grey), then go to B (grey), then C goes grey, then D goes grey. D's neighbor is B, and B's color is grey, which means you've found a back edge confirming the cycle B to C to D to B.

Now consider a non-cyclic case to see why two colors aren't enough. The edges are A to B, A to C, B to D, C to D. You start from A, go to B, then go to D. You mark D black, then mark B black. Back to A, you go to C, and C's neighbor D is already black, so there's no cycle. With only visited/unvisited, D would look like a cycle when reached from C because it was "already visited." Three colors correctly distinguish "currently in progress" from "finished."

Practicing directed and undirected detection in alternation, rather than learning one completely before starting the other, builds stronger discrimination between when each method applies. The research on interleaving backs this up pretty consistently.

Union Find for undirected cycle detection

DFS isn't the only option for undirected graphs. Union Find (Disjoint Set Union) works differently, and it's especially useful when your graph arrives as a list of edges rather than an adjacency list.

You process edges one at a time. For each edge (u, v), you check if u and v already belong to the same connected component. If they do, this edge creates a cycle. If they don't, merge their components.

When does Union Find beat DFS? There are two main scenarios. First, when the graph is given as an edge list and you'd need to build an adjacency list just to run DFS, Union Find processes edges directly. Second, when you're building the graph incrementally and need cycle checks as you add edges. Each union call is nearly O(1) with path compression and union by rank, so cycle detection is essentially constant-time per edge.

The trade-off matters though. Union Find only works for undirected graphs. It can't detect cycles in directed graphs because it has no concept of edge direction. It treats the graph as a collection of connected components, and that's an inherently undirected abstraction.

The connection to topological sort

Topological sort produces a linear ordering of nodes where every directed edge points "forward." This only works if the graph has no cycles. A cycle means node A must come before B, B before C, and C before A. No linear ordering can satisfy that contradiction.

The connection runs both ways. You can detect cycles in a directed graph by attempting a topological sort. If the sort produces fewer nodes than the graph contains, there's a cycle.

That's where Kahn's algorithm comes in.

Kahn's algorithm (BFS-based topological sort) starts with all nodes that have zero in-degree, removes them, updates in-degrees, and repeats. If a cycle exists, the nodes in the cycle never reach in-degree zero. They're stuck waiting on each other.

For a deeper look at how BFS and DFS compare across graph problems, including when each traversal strategy is the right fit, see the BFS vs DFS comparison. The broader graph algorithms landscape, from shortest paths to connected components, is covered in the complete graph algorithms guide.

Which algorithm for which graph

Here's a quick decision framework you can use.

The three methods are distinct, but the underlying question is the same. Can I reach a node that I'm currently in the process of exploring? For undirected graphs, "in the process of exploring" means "visited but not my direct parent." For directed graphs, it means "grey in the three-color system." For Union Find, it means "already in the same component."

Six months ago, you'd open a cycle detection problem and try to remember which version you'd last memorized. The directed vs undirected distinction felt like a footnote. Now you recognize it is the algorithm. You see an undirected graph and your first instinct is parent tracking, because you understand why bidirectional edges produce false positives. You see a directed graph and you reach for three colors, because you know a finished node and a node in progress are different states that need different treatment.

Codeintuition's Graph course covers cycle detection in both directed and undirected graphs from first principles. The undirected detection lesson and directed detection lesson each build the reasoning before the implementation. Union Find, topological sort, and all five graph patterns follow the same construction-first model across 40 lessons. The free tier covers complete courses on Arrays and Singly Linked Lists, where the same first-principles approach applies to foundational patterns like two pointers and fast-slow pointers.

The first time you pick the right cycle detection method without checking which one a problem expects, you'll know the understanding is there.