Detect Cycles in a Graph

A cycle in a graph is a sequence of edges and vertices where you can start from a specific vertex, follow a continuous path, and return to the same vertex without repeating any edge. In simpler terms, a cycle occurs when you can start at a vertex, traverse a set of edges, and return to the same vertex without retracing any edge.

Detecting cycles in a graph is crucial for several reasons. It helps identify potential problems like deadlocks in operating systems, ensures the reliability of dependency management in software development, and prevents infinite loops in network routing protocols.

Various algorithms have been developed to detect cycles in a graph, each with different approaches and efficiencies. Depth-First Search (DFS) is a common method that uses a recursive approach to explore all possible paths from a vertex and backtracks upon revisiting any vertex, thereby identifying cycles. Another popular algorithm is the Union-Find algorithm, which is effective in detecting cycles in undirected graphs by maintaining a disjoint-set data structure.

In this article we will look at DFS based algorithms to detect cycles in directed and un-directed graphs.

Detect Cycles in an Undirected Graph

Here’s the algorithm to detect cycles in an undirected graph:

1. Perform a depth-first search (DFS) traversal starting from each unvisited vertex
2. During DFS traversal, mark current vertex as visited
3. For each unvisited neighbor from the current vertex:
   • If the neighbor vertex is not visited, perform DFS on this vertex
   • If the neighbor vertex is already visited, it means there is a cycle

Below is the implementation:

Detect Cycles in an directed Graph

Here’s an algorithm to detect cycles in a directed graph using the white, gray, and black (0, 1, 2) marking technique:

1. Initialize all vertices in the graph as white (0).
2. Perform a depth-first search (DFS) traversal starting from vertices still marked as white.
3. During the DFS traversal, mark each vertex as follows:
   • When a vertex is first visited, mark it as gray (1).
   • When the DFS has finished exploring all the vertices reachable from the current vertex, mark it as black (2).
4. If, during the DFS traversal, a gray vertex is encountered, it means a cycle has been detected.

Below is the implementation: