In computer science, detecting cycles in a directed graph is a fundamental problem with applications in various areas such as deadlock detection, scheduling, and more. Here's a comprehensive guide on how to detect if a directed graph is cyclic.

Understanding Directed Graphs and Cycles

A directed graph or digraph consists of nodes (or vertices) connected by edges where each edge has a direction, indicating a one-way relationship between two nodes. A cycle in a directed graph occurs when there is a path from a node to itself following the direction of the edges.

Example of Directed Cycle

Consider the directed graph with nodes A , B , and C and edges A -> B , B -> C , and C -> A . This graph contains a cycle since you can start at A , follow the edges A -> B -> C -> A , and return to the starting node.

Techniques to Detect Cycles

Here, we describe two primary techniques to detect cycles in a directed graph: Depth First Search (DFS) and Kahn's Algorithm.

1. Cycle Detection Using Depth First Search (DFS)

DFS is a classic recursive algorithm used to explore all nodes and edges of a graph. In cycle detection, DFS visits nodes and tracks the states of vertices: unvisited, visiting, and visited.

• Unvisited: Node has not been processed.
• Visiting: Node is currently being processed; all its descendants are not fully processed yet.
• Visited: Node and all its descendants have been processed.

Steps:

1. Initialize all nodes as unvisited.
2. For each unvisited node, perform DFS:
   • Mark the node as visiting.
   • Recursively visit all adjacent unvisited nodes.
   • Mark the node as visited.
3. If you encounter a node that is currently visiting, a cycle exists.
   • Remove a node from the queue and reduce the in-degree of its neighbors by 1.
   • If any neighbor’s in-degree becomes zero, add it to the queue.

• Complexity: Both algorithms mentioned above run in $O(V + E)$ time complexity, where $V$ is the number of vertices and $E$ is the number of edges.
• Space Efficiency: DFS uses additional space for recursion stack, while Kahn’s algorithm uses a queue.