Cycle Detection in Graphs

Detecting cycles is a fundamental problem in graph theory with applications in areas like deadlock detection in operating systems and verifying the integrity of data structures. The approach to cycle detection depends on whether the graph is directed or undirected.

Undirected Graphs

For an undirected graph, you can use either DFS or BFS to detect cycles. A common method with DFS is to keep track of the parent of the current node in the traversal. If you encounter a visited node that is not the parent of the current node, you have found a cycle. The Union-Find data structure is also an effective tool for cycle detection in undirected graphs.

Directed Graphs

In a directed graph, a cycle exists if there is a "back edge" – an edge that leads from a node to one of its ancestors in the DFS tree. To detect this, we can use DFS and maintain three sets of vertices: white (unvisited), gray (visiting), and black (visited). A cycle is detected if the DFS traversal encounters a gray node.

Another way to detect a cycle in a directed graph is to use Topological Sort. If a topological sort is possible and includes all vertices, the graph is a DAG (and has no cycles). If the sort includes fewer vertices than the total, the graph must contain at least one cycle.