Cycle Detection

Cycle detection determines whether a graph contains a cycle, a path that returns to its starting vertex. The techniques differ between directed graphs, where cycles mean circular dependencies, and undirected graphs, where any extra edge beyond a tree creates a cycle.

How it works

In directed graphs, DFS classifies edges: a back edge to a vertex still on the recursion stack proves a cycle, tracked with three vertex states (unvisited, in progress, done). In undirected graphs, DFS finds a cycle when it meets a visited vertex other than its parent, and Union-Find detects one when an edge joins two vertices already in the same set. All approaches run in O(V + E), with Union-Find nearly constant per edge.

Applications

Cycle detection prevents deadlocks in operating systems, catches circular imports in build tools and package managers, validates spreadsheets and workflow definitions, and is the gatekeeper for topological sorting. Floyd's tortoise-and-hare variant for linked lists is one of the most asked interview questions of all.