Introduction 

In this article, we will learn about Cycle Detection in Directed Graph using multiple approaches. 

Examine a directed graph to see if it has a cycle. If the given graph contains at least one cycle, your function should return true; otherwise, it should return false.

Method 1:

DFS Approach

A cycle in a graph can be detected using Depth First Traversal. A tree is produced using DFS for a connected graph. Only if the graph has a rear edge does it have a cycle. A back edge in the DFS tree is an edge that connects a node to itself (self-loop) or one of its ancestors.

Get the DFS forest as output for a disconnected graph. Check for a cycle in individual trees by looking at the back borders.

Keep track of the vertices currently in the recursion stack of the DFS traversal algorithm to detect a back edge. There is a cycle in the tree if a vertex is reached that is already on the recursion stack. A back edge connects the current vertex to the next vertex in the recursion stack. To keep track of vertices in the recursion stack, use the recStack[] array.

Algorithm:

• Create the graph using the given number of edges and vertices.
• Create a recursive function that initializes the current index or vertex, visited, and recursion stack.
• Mark the current node as visited and also mark the index in the recursion stack.
• Find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, If the recursive function returns true, return true.
• If the adjacent vertices are already marked in the recursion stack then return true.
• Create a function, that calls the recursive function for all the vertices, and if any function returns true return true. Else if for all vertices the function returns false return false.

C++ code:

#include<bits/stdc++.h> 
using namespace std; 

bool isCyclicUtil(int v, vector<bool> &visited, vector<bool> &recStack, vector<int> adj[]){

    if(visited[v] == false) { 

visited[v] = true; 
recStack[v] = true; 
 
//calling function recursively for all the vertices adjacent to this vertex.

for(int i = 0; i < adj[v].size(); ++i) { 

if ( !visited[adj[v][i]] && isCyclicUtil(adj[v][i], visited, recStack, adj)) 

return true; 

else if (recStack[adj[v][i]]) 

return true; 

  } 

} 

recStack[v] = false;    //removing the vertex from recursion stack

return false; 
}
 
bool isCyclic(int V, vector<int> adj[]){

vector<bool> visited(V, false); 

vector<bool> recStack(V, false); 

for(int i = 0; i < V; i++) 

if(isCyclicUtil(i, visited, recStack, adj)) 

return true;

return false;

// Returns true if the graph contains a cycle, else false.

}
 
void addEdge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
}

 
int main() { 

int V=5;

vector<int> adj[V];

addEdge(adj,0, 1);  // creating the graph by connecting the edges

    addEdge(adj,4, 1); 
    addEdge(adj,1, 2); 
    addEdge(adj,2, 3); 
    addEdge(adj,3, 1);    

    if(isCyclic(V, adj))
        cout<<"There exists a cycle in the graph\n";
    else
        cout << "There exists no cycle in the graph\n"; 
return 0; 
} 

Output:

There exists a cycle in the graph

Time Complexity: O(+E). 

The Time Complexity of this method is the same as the time complexity of DFS traversal which is O(V+E).

Space Complexity: O(V). 

To store the visited and recursion stack O(V) space is needed.

Where E is the number of edges and V is the no. of vertices in the graph.

Method 2:

BFS Algo using Kahn’s algorithm.

Now let’s see Kahn’s algorithm.

Khan’s Algorithm:

For a Directed Acyclic Graph (DAG), topological sorting is a linear ordering of vertices in which vertex u occurs before v in the ordering for any directed edge uv. If the graph is not a DAG, topological sorting is not possible.

A topological ordering of the network below, for example, is "5 4 2 3 1 0? A graph can have more than one topological sorting. Another topological sorting of the above graph, for example, is "4 5 2 0 3 1′′. In topological sorting, the initial vertex is usually a vertex with an in-degree of 0. (a vertex with no incoming edges).

Let's see BFS (Kahn's Algorithm) based Solution also:

In this approach, we use khan’s algorithm to check if the count of all the nodes included in the topo sort is equal to the total number of nodes, then the cycle does not exist otherwise there will be a cycle in the graph.

// Time Complexity: O(V + E)
// Space Complexity: O(V)

#include<bits/stdc++.h> 
using namespace std; 
 
void topologicalSort(vector<int> adj[], int V) { 
    vector<int> in_degree(V, 0);  

    for (int u = 0; u < V; u++) { 
        for (int x:adj[u]) 
            in_degree[x]++; 
    }   

    queue<int> q; 
    for (int i = 0; i < V; i++) 
        if (in_degree[i] == 0) 
            q.push(i);  

    int count=0;  
    while (!q.empty()) { 
        int u = q.front(); 
        q.pop();   

        for (int x: adj[u]) 
            if (--in_degree[x] == 0) 
                q.push(x); 
        count++;
    } 

    if (count != V) // If graph contains the cycle.
        cout << "There exists a cycle in the graph\n"; 
    else  // If graph does not contains the cycle
        cout << "There exists no cycle in the graph\n";
}
 
void addEdge(vector<int> adj[], int u, int v){
    adj[u].push_back(v);
}
 
int main() { 
int V=5;
vector<int> adj[V];
addEdge(adj,0, 1); // creating the graph by connecting the edges
    addEdge(adj,4, 1); 
    addEdge(adj,1, 2); 
    addEdge(adj,2, 3); 
    addEdge(adj,3, 1);    
    topologicalSort(adj,V); 
return 0; 
} 

Output:

There exists a cycle in the graph