cycledetection

Cycle detection is the problem of determining whether a graph contains a cycle, a closed path where the starting and ending vertices coincide and no edges or, depending on definition, vertices are repeated along the way. Cycle detection is distinguished by whether the input graph is directed or undirected, as the presence and meaning of cycles differ between the two.

In directed graphs, a common approach is depth-first search with color marking or a recursion stack. During DFS, encountering a edge to a currently active (gray) vertex indicates a directed cycle. Tarjan’s strongly connected components can also reveal cycles, since any component with more than one vertex or a self-loop indicates a cycle. A topological sort can detect cycles by failing to produce a full ordering when a cycle exists. The typical time complexity is O(V + E) and space O(V).

In undirected graphs, cycle presence can be detected with DFS while tracking the parent edge, because visiting a previously seen vertex that is not the parent indicates a cycle. Union-Find (disjoint-set) can detect cycles during edge additions: if an edge connects two vertices already in the same set, a cycle exists. These methods also run in O(V + E) time with linear or near-linear space.

Applications of cycle detection include deadlock detection in operating systems, verification of circuit designs, dependency resolution in build systems, scheduling and resource management, and analysis of network topologies. Limitations can arise in dynamic or incremental graphs, where cycles may appear or disappear as edges are added or removed.