Go back

Cycle Detection in a Graph

Last updated: Mon May 12 2025

Cycle detection is a classic problem in graph theory—and one with powerful real-world relevance. From detecting deadlocks in operating systems to breaking dependency loops in build systems, being able to spot cycles is essential.

For software engineers, especially those preparing for coding interviews, this topic is a must-know. Interviewers often use it to test your understanding of graph traversal, recursion, state tracking, and data structures like Union-Find. In this post, we’ll walk through the most important techniques for cycle detection and explain when to use each.

Depth-First Search (DFS)

One of the most intuitive ways to detect a cycle in a directed graph. You maintain a set of nodes currently in the recursion stack. If you revisit a node that’s already in that set, you’ve found a cycle.

Kahn’s Algorithm (Topological Sorting)

Designed for directed graphs, this algorithm removes nodes with in-degree 0 one at a time. If you can’t process all nodes, there’s a cycle.

Union-Find (Disjoint Set Union)

Perfect for undirected graphs. If you attempt to union two nodes that already belong to the same set, a cycle exists.

Floyd’s Cycle Detection (Tortoise and Hare)

Best known for detecting loops in linked lists, but adaptable to graphs under specific conditions. Uses two pointers moving at different speeds.

Color-Based DFS

A variation of DFS that uses color marking:

Revisiting a gray node signals a cycle.

Breadth-First Search (BFS)

Less common for cycle detection, but in undirected graphs, revisiting a previously seen node (not the parent) can signal a cycle.

Edge Classification in DFS

During DFS, edges are classified as:

A back edge to an ancestor in the DFS tree reveals a cycle.

Matrix-Based Methods

For small graphs, you can use matrix exponentiation. If the diagonal of the adjacency matrix A^n has a non-zero entry, there is a cycle.

Dynamic Programming

Used for specialized problems like detecting cycles of length k. Not practical for general use but useful in constrained environments.

Graph Coloring (Bipartite Check)

Try coloring an undirected graph using two colors. If it’s not possible, an odd-length cycle is present.

Conclusion

Cycle detection is more than a textbook algorithm—it’s essential in systems, scheduling, and interviews. By understanding multiple techniques, you’ll be ready to choose the right approach for the graph type and problem constraints.

For interviews, focus on:

Mastering these will prepare you for many variations of graph problems and help you stand out in technical interviews.