Cycle Detection in Directed and Undirected Graphs
Learn how to detect cycles in both directed and undirected graphs. Understand DFS-based detection using colors, back edges, and union-find approaches with clear examples.
Detailed Explanation
Cycle Detection in Graphs
A cycle exists when you can start at a node and follow edges to return to that same node. Detecting cycles is essential for deadlock detection, dependency validation, and determining whether topological sorting is possible.
Cycle Detection in Undirected Graphs
In an undirected graph, a cycle is detected during DFS when you encounter a visited node that is not the parent of the current node.
DFS from A:
A → B → C → A? (C sees A, but A is not C's parent → CYCLE)
Union-Find approach: For each edge (u, v), check if u and v are in the same set. If yes, adding this edge creates a cycle. If no, union them.
Cycle Detection in Directed Graphs
In a directed graph, use the three-color algorithm:
- White (unvisited) — Not yet discovered
- Gray (in progress) — Currently being explored (on the recursion stack)
- Black (finished) — Fully explored, all descendants processed
A back edge — an edge from a gray node to another gray node — indicates a cycle.
DFS with colors:
A(gray) → B(gray) → C(gray) → A(gray) → CYCLE (back edge C→A)
Time Complexity
Both approaches run in O(V + E) time, which is optimal since every node and edge must be examined at least once in the worst case.
Why It Matters
- DAG validation — Topological sort only works on acyclic directed graphs
- Deadlock detection — Resource allocation graphs with cycles indicate deadlocks
- Package managers — Circular dependencies must be detected and reported
Use Case
Build systems (Make, Gradle, Bazel) use cycle detection to ensure there are no circular dependencies before computing a build order. Operating systems detect deadlocks by checking for cycles in resource allocation graphs. Package managers (npm, pip) check for circular dependency chains. Version control systems detect merge conflicts that create logical cycles in branch histories.