Detect Cycle in Directed Graph

Examples

Example 1

Input:

Output: NO

Explanation:

No cycle exists in the above give Directed graph, hence we printed "NO" as the output.

Example 2

Input:

Output: YES

Explanation: There exists a cycle $0\rightarrow 1\rightarrow3 \rightarrow 4 \rightarrow 1$, hence we had printed "YES" in the output.

Constraints

$1\leq V, E\leq 10^5$

Approach 1: Using Depth First Search (DFS)

To detect the cycle in a directed graph, we will be using the DFS technique. We know that the DFS of the directed graph generates a DFS tree(s), which is nothing but the representation of vertices and edges of the provided graph.

When we perform DFS on a disconnected graph, multiple such trees hence we use the term DFS Forest to denote all of them. Each of these trees has a certain different type of edges that are -

1. Tree Edge
2. Forward Edge
3. Cross Edge
4. Back Edge

Here to detect the cycle in a directed graph, we are only concerned about the Back Edge. Back Edge is an edge that connects a vertex (say $u$) to one of its descendants. Let us understand the concept of back edge through an example - Consider the following graph and its DFS tree obtained by performing DFS starting from vertex $A$

It is easily noticeable that due to the presence of the back edge we can form a cycle $B\rightarrow C\rightarrow D \rightarrow B$. So it is understood that the presence of a back edge indicates there is a cycle in the graph.

Now we will how we can use the DFS to find whether there exists a back edge. To detect the back edge we will keep track of vertices currently present in the recursion stack of the DFS function. If we encounter a vertex that is present in the recursion stack, we can say a back edge is present and there exists a cycle in the graph.

The algorithm is as follows -

• Let $DFS$ be boolean type recursive function, accepting three arguments $i.e.$ the vertex number (say node), visited array, and inStack array.
• In the function, firstly we will check if node is already present in the recursion stack. If found true, a cycle exists in the graph.
• After that, we will proceed if node has not been visited in the previous DFS call(s).
• We will mark node and then recurse for all the neighbors of node.

Dry Run

Let's use the graph used in Example 2 to do a dry run of this approach. Graph -

Proceeding as per the algorithm -

• Define visited and inStack array to keep track of visited vertices and vertices present in the recursive stack respectively. So we have
  • visited[] = [F, F, F, F, F]
  • inStack[] = [F, F, F, F, F] Note that F means False and T means True.
• Start DFS from vertex $0$. Mark $0$ as visited and to be present in the recursive stack. Now we will recurse for one of the adjacents of $0$ i.e. $1$ and $2$. Let's say we recurse for $2$ first with our arrays as
  • visited[] = [T, F, F, F, F]
  • inStack[] = [T, F, F, F, F]
• Mark $2$ as visited and to be present in recursive stack. After that, we will recurse for only adjacent of $2$ i.e. $3$ with our arrays as -
  • visited[] = [T, F, T, F, F]
  • inStack[] = [T, F, T, F, F]
• Mark $3$ as visited and to be present in the recursive stack. After that we will recurse for only adjacent of $3$ i.e. $4$ with our arrays as -
  • visited[] = [T, F, T, T, F]
  • inStack[] = [T, F, T, T, F]
• Mark $4$ as visited and to be present in the recursive stack. After that, we will recurse for one of the adjacents of $4$ Viz. $0$ and $2$. No matter for which one we recurse, we will find the cycle let's see how.
  • Choice 1 - Recurse for vertex $0$ We find that inStack[0] is true, which means it is present in the recursive stack, hence we can conclude cycle exists.
  • Choice 2 - Recurse for vertex $2$ We find that inStack[2] is also True, which means it is present in the recursive stack, hence we can conclude cycle exists.

It is clear from the dry run that a cycle exists in the graph. We would strongly recommend you to pick a pen and paper and dry run this approach for the graph of example 1.

Pseudocode

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

• Time Complexity - Since we are doing a DFS traversal with some minor modifications, the time complexity in the worst case (when the cycle does not exists) is O(V+E).
• Space Complexity - We are using boolean arrays of size V, and maximum recursive stack height can reach up to V. Therefore, the space complexity is O(V).

Approach 2: Using Breadth First Search (BFS)

In the previous section, we have seen how we can detect a cycle in a directed graph using Depth First Search. In this section, we will be seeing how we can detect a cycle in directed graph using the Breadth First Search technique.

The idea is very simple, we learned in Topological Sorting that, topological sort is possible only if the graph is DAG (Directed Acyclic Graph) $i.e.$ Graph should be directed and it should not contain any cycle. Therefore we will just check if the topological ordering is possible for the given graph or not.

To check if topological ordering is possible or not, we will use Kahn's Algorithm which uses the idea of indegrees of the vertices where the in-degree of a vertex (say $v$) is nothing but the number of incoming edges toward the vertex $v$.

The algorithm is as follows -

• Define an array (sat deg) of size $V$, which will be used to store indegrees of the vertices.
• Compute indegrees of all the vertices by iterating over the adjacency list provided as the input.
• Define a Queue (say q), and insert all the vertices with indegree 0.
• Define a variable (say counter) and initialize it with 0, this will be used to count the number of processed vertices.
• Iterate using a while loop, until $q$ is not empty and do the following -
  • Dequeue element from the queue and store it in a variable (say u).
  • Now increase the counter by 1, because u is considered to be processed.
  • Now iterate over all the adjacents of u and do the following -
    • Let adjacent be v.
    • Decrease the indegree of v.
    • If indegree of v reaches 0, add v to the q.
• If the condition counter = V holds true, it means the graph does not contain any cycle otherwise cycle is present.

To understand the above algorithm more clearly, we will dry run this algorithm on the below sample graph (same as given in the examples section)

Dry Run

Graph -

• Step 1 - Calculate Indegrees After calculating the indegrees, we have deg = [0, 2, 2, 2, 1]
• Step 2 - Insert vertices with 0 indegrees in q. We have only one vertex with indegree as 0, so we will insert that in q. After which we have q = [0]. Note that q contains the number of the vertices.
• Step 3 - Iterating until q is not empty
  • Iteration 1 -
    • Dequeue the vertex $\implies$ v = 0
    • Increase counter by 1.
    • Iterate over all adjacent of 0 and reduce indegree by 1. After which we have deg = [0, 1, 1, 2, 0]
    • Insert 4 in q because deg[4] = 0. After which we have q = [4]
  • Iteration 2 -
    • Dequeue the vertex $\implies$ v = 4
    • Increase counter by 1.
    • Iterate over all adjacent of 4 and reduce indegree by 1. After which we have deg = [0, 0, 0, 2, 0]
    • Insert 1 and 2 in q because deg[1]=0 and deg[2]=0. After which we have q = [1, 2]
  • Iteration 3 -
    • Dequeue the vertex $\implies$ v = 1
    • Increase counter by 1.
    • Iterate over all adjacent of 1 and reduce indegree by 1. After which we have deg = [0, 0, 0, 1, 0]
    • Now we have q = [2]
  • Iteration 4 -
    • Dequeue the vertex $\implies$ v = 2
    • Increase counter by 1.
    • Iterate over all adjacent of 3 and reduce indegree by 1. After which we have deg = [0, 0, 0, 0, 0]
    • Insert 3 in q because deg[3]=0. After which we have q = [3]
  • Iteration 5 -
    • Dequeue the vertex $\implies$ v = 3
    • Increase counter by 1.
    • Vertex 3 does not have any adjacent vertices.
    • Now we have q = [].
• Step 4 - Check if counter = V This condition holds true because after Step 3 we have counter = 5 and as per the input V = 5. So we will print "NO".

We would strongly recommend you to Pick a pen and paper and dry run the algorithm on the graph provided in Example 2.

Pseudocode

Java Implementation

C++ Implementation

Python Implementation

Complexity Analysis

• Time Complexity - The Time required to find indegrees of vertices is O(E) and finding vertices with 0 indegrees is O(V), also O(V) time is required in the while loop. Therefore overall time complexity is O(E + V + V) which is nothing but O(V + E).
• Space Complexity - Since, we are using a deg array of size V and a Queue that can reach a size up to V. Hence, the overall space complexity is O(V).