Detect a cycle in a directed graph

Intuition:

In a Directed Cyclic Graph, during traversal, if we end up at a node, that we have visited previously in the path, that means we came around a circle and ended up at this node, which determines that it has a cycle. However, detecting cycles using DFS in directed graphs requires a different approach than in undirected graphs due to the nature of directed edges.

Understanding:

In undirected graphs, detecting cycles involves checking if a visited node is not the parent of the current node. On the other hand, in directed graphs, simply finding a previously visited node isn't enough because it might have been visited via a different path.
To accurately detect cycles in a directed graph, we need to track nodes within the current path of the DFS traversal. This means maintaining a path array to keep track of nodes in the current DFS path.
If we encounter a node that is already in the current DFS path (recursion stack), it indicates a cycle. If a node is visited but not in the current DFS path, it doesn’t necessarily indicate a cycle.

Approach:

A helper function performs DFS, where during the traversal, the nodes are marked as visited and path visited.
During the traversal, the cycles are checked by detecting if a node is revisited in the current path. Unmarks the node in the path visited array after exploration.
Traverse all the components in the graph to detect the cycle. If any of the components contains a cycle, return true. Otherwise, if no cycle is detected, return false.

Dry Run:

Solution:

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

class Solution {
private:

    // Function to perform DFS traversal
    bool dfs(int node, vector<int> adj[], 
             vector<bool> &visited, 
             vector<bool> &pathVisited) {
                 
        // Mark the node as path visited
        visited[node] = true;
        
        // Mark the node as path visited
        pathVisited[node] = true;
        
        // Traverse all the neighbors
        for(auto it : adj[node]) {
            
            /* If the neighbor is already visited 
            in the path, a cycle is detected */
            if(pathVisited[it]) 
                return true;
            
            /* Else if the node is unvisited, 
            perform DFS recursively from this node */
            else if(!visited[it]) {
                
                // If cycle is detected, return true
                if(dfs(it, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        // Remove the node from path 
        pathVisited[node] = false;
        
        // Return false if no cycle is detected
        return false;
    }
    
public:

    // Function to detect cycle in a directed graph.
    bool isCyclic(int V, vector<int> adj[]) {
        
        // Visited array
        vector<bool> visited(V, false);
        
        /* Array to mark nodes that are 
        visited in a particular path */
        vector<bool> pathVisited(V, false);
        
        // Traverse the graph
        for(int i=0; i<V; i++) {
            if(!visited[i]) {
                
                // If a cycle is found, return true
                if(dfs(i, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        /* Return false if no cycle is 
        detected in any component */
        return false;
    }
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
        {1}, 
        {2, 5}, 
        {3}, 
        {4}, 
        {1},
        {} 
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine if cycle 
    exists in given directed graph */
    bool ans = sol.isCyclic(V, adj);
    
    // Output
    if(ans)
        cout << "The given directed graph contains a cycle.";
    else 
        cout << "The given directed graph does not contain a cycle.";
    
    return 0;
}
import java.util.*;

class Solution {
    
    // Function to perform DFS traversal
    private boolean dfs(int node, List<Integer> adj[], 
                        boolean[] visited, 
                        boolean[] pathVisited) {
        
        // Mark the node as path visited
        visited[node] = true;
        
        // Mark the node as path visited
        pathVisited[node] = true;
        
        // Traverse all the neighbors
        for(int it : adj[node]) {
            
            /* If the neighbor is already visited 
            in the path, a cycle is detected */
            if(pathVisited[it]) 
                return true;
            
            /* Else if the node is unvisited, 
            perform DFS recursively from this node */
            else if(!visited[it]) {
                
                // If cycle is detected, return true
                if(dfs(it, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        // Remove the node from path 
        pathVisited[node] = false;
        
        // Return false if no cycle is detected
        return false;
    }
    
    // Function to detect cycle in a directed graph.
    public boolean isCyclic(int V, List<Integer> adj[]) {
        
        // Visited array
        boolean[] visited = new boolean[V];
        
        /* Array to mark nodes that are 
        visited in a particular path */
        boolean[] pathVisited = new boolean[V];
        
        // Traverse the graph
        for(int i = 0; i < V; i++) {
            if(!visited[i]) {
                
                // If a cycle is found, return true
                if(dfs(i, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        /* Return false if no cycle is 
        detected in any component */
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        
        int V = 6;
        List<Integer> adj[] = new List[V];
        for(int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        
        adj[0].add(1); 
        adj[1].add(2); adj[1].add(5);
        adj[2].add(3);
        adj[3].add(4);
        adj[4].add(1);
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to determine if cycle 
        exists in given directed graph */
        boolean ans = sol.isCyclic(V, adj);
        
        // Output
        if(ans)
            System.out.println("The given directed graph contains a cycle.");
        else 
            System.out.println("The given directed graph does not contain a cycle.");
    }
}
class Solution:
    # Function to perform DFS traversal
    def dfs(self, node, adj, visited, pathVisited):
        # Mark the node as path visited
        visited[node] = True
        
        # Mark the node as path visited
        pathVisited[node] = True
        
        # Traverse all the neighbors
        for it in adj[node]:
            
            # If the neighbor is already visited 
            # in the path, a cycle is detected
            if pathVisited[it]:
                return True
            
            # Else if the node is unvisited, 
            # perform DFS recursively from this node
            elif not visited[it]:
                
                # If cycle is detected, return true
                if self.dfs(it, adj, visited, pathVisited):
                    return True
        
        # Remove the node from path 
        pathVisited[node] = False
        
        # Return false if no cycle is detected
        return False

    # Function to detect cycle in a directed graph.
    def isCyclic(self, V, adj):
        
        # Visited array
        visited = [False] * V
        
        # Array to mark nodes that are 
        # visited in a particular path
        pathVisited = [False] * V
        
        # Traverse the graph
        for i in range(V):
            if not visited[i]:
                
                # If a cycle is found, return true
                if self.dfs(i, adj, visited, pathVisited):
                    return True
        
        # Return false if no cycle is 
        # detected in any component
        return False

if __name__ == "__main__":
    
    V = 6
    adj = [[] for _ in range(V)]
    adj[0].append(1)
    adj[1].extend([2, 5])
    adj[2].append(3)
    adj[3].append(4)
    adj[4].append(1)
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to determine if cycle 
    # exists in given directed graph
    ans = sol.isCyclic(V, adj)
    
    # Output
    if ans:
        print("The given directed graph contains a cycle.")
    else:
        print("The given directed graph does not contain a cycle.")
class Solution {
    
    // Function to perform DFS traversal
    dfs(node, adj, visited, pathVisited) {
        // Mark the node as path visited
        visited[node] = true;
        
        // Mark the node as path visited
        pathVisited[node] = true;
        
        // Traverse all the neighbors
        for(let it of adj[node]) {
            
            /* If the neighbor is already visited 
            in the path, a cycle is detected */
            if(pathVisited[it]) 
                return true;
            
            /* Else if the node is unvisited, 
            perform DFS recursively from this node */
            else if(!visited[it]) {
                
                // If cycle is detected, return true
                if(this.dfs(it, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        // Remove the node from path 
        pathVisited[node] = false;
        
        // Return false if no cycle is detected
        return false;
    }
    
    // Function to detect cycle in a directed graph.
    isCyclic(V, adj) {
        
        // Visited array
        let visited = new Array(V).fill(false);
        
        /* Array to mark nodes that are 
        visited in a particular path */
        let pathVisited = new Array(V).fill(false);
        
        // Traverse the graph
        for(let i = 0; i < V; i++) {
            if(!visited[i]) {
                
                // If a cycle is found, return true
                if(this.dfs(i, adj, visited, pathVisited)) 
                    return true;
            }
        }
        
        /* Return false if no cycle is 
        detected in any component */
        return false;
    }
}

const main = () => {
    
    let V = 6;
    let adj = [
        [1], 
        [2, 5], 
        [3], 
        [4], 
        [1],
        [] 
    ];
    
    /* Creating an instance of 
    Solution class */
    let sol = new Solution(); 
    
    /* Function call to determine if cycle 
    exists in given directed graph */
    let ans = sol.isCyclic(V, adj);
    
    // Output
    if(ans)
        console.log("The given directed graph contains a cycle.");
    else 
        console.log("The given directed graph does not contain a cycle.");
}

main();

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
A simple DFS traversal takes O(V+E) time.

Space Complexity: O(V)
The visited array and Path Visited array take O(V) space each and the recursion stack space during DFS traversal will be O(V).

Intuition:

To solve this problem using BFS traversal, the previously known algorithm Topological Sort can be used.

Recall that Topological Ordering for a graph having V nodes can be determined if and only the graph is a Directed Acyclic Graph, i.e., there must be no cycle present in the directed graph. In other words, the topological ordering of a DAG consisting of V nodes will always contain V nodes.

But this is not true in the case of a Directed Cyclic Graph. In such a graph where the number of nodes is V, the topological ordering will not contain all nodes (because of the presence of a cycle).

Thus, if the topological sort of the directed graph contains all nodes of the graph, then the graph is acyclic otherwise it is cyclic.

Approach:

A helper function is defined to get the topological sort for the given graph using Kahn's algorithm (BFS based).
The topological ordering for the given directed graph is found using the helper function.
If the ordering contains all nodes, the directed graph is cyclic. Otherwise it is acyclic.

Dry Run:

Solution:

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

class Solution {
private:
    /* Function to return the topological
     sorting of given graph */
    vector<int> topoSort(int V, vector<int> adj[]) {
        
        // To store the result
        vector<int> ans;
        
        // To store the In-degrees of nodes
	    vector<int> inDegree(V, 0);
	    
	    // Calculating the In-degree of the given graph
	    for(int i=0; i<V; i++) {
	        for(auto it : adj[i]) inDegree[it]++;
	    }
	    
	    // Queue to facilitate BFS
	    queue<int> q;
	    
	    // Add the nodes with no in-degree to queue
	    for(int i=0; i<V; i++) {
	        if(inDegree[i] == 0) q.push(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.empty()) {
	        
	        // Get the node
	        int node = q.front();
	        
	        // Add it to the answer
	        ans.push_back(node);
	        q.pop();
	        
	        // Traverse the neighbours
	        for(auto it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.push(it);
	        }
	    }
	    
	    // Return the result
	    return ans;
    }
    
public:
    // Function to detect cycle in a directed graph.
    bool isCyclic(int V, vector<int> adj[]) {
        
        // To store the topological ordering
        vector<int> topo;
        
        // Get the topological sort of the graph
        topo = topoSort(V, adj);
        
        /* If topological sort doesn't include all
        nodes, the graph is cyclic in nature. */
        if(topo.size() < V) return true;
        
        // Else the graph is acyclic. 
        return false;
    }
};

int main() {
    
    int V = 6;
    vector<int> adj[V] = {
        {1}, 
        {2, 5}, 
        {3}, 
        {4}, 
        {1},
        {} 
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine if cycle 
    exists in given directed graph */
    bool ans = sol.isCyclic(V, adj);
    
    // Output
    if(ans)
        cout << "The given directed graph contains a cycle.";
    else 
        cout << "The given directed graph does not contain a cycle.";
    
    return 0;
}
import java.util.*;

class Solution {
    
    /* Function to return the topological
     sorting of given graph */
    private List<Integer> topoSort(int V, 
                    List<Integer> adj[]) {
                        
        // To store the result
        List<Integer> ans = new ArrayList<>();
        
        // To store the In-degrees of nodes
        int[] inDegree = new int[V];
        
        // Calculating the In-degree of the given graph
        for(int i = 0; i < V; i++) {
            for(int it : adj[i]) inDegree[it]++;
        }
        
        // Queue to facilitate BFS
        Queue<Integer> q = new LinkedList<>();
        
        // Add the nodes with no in-degree to queue
        for(int i = 0; i < V; i++) {
            if(inDegree[i] == 0) q.add(i);
        }
        
        // Until the queue is empty
        while(!q.isEmpty()) {
            // Get the node
            int node = q.poll();
            
            // Add it to the answer
            ans.add(node);
            
            // Traverse the neighbours
            for(int it : adj[node]) {
                // Decrement the in-degree
                inDegree[it]--;
                
                /* Add the node to queue if 
                its in-degree becomes zero */
                if(inDegree[it] == 0) q.add(it);
            }
        }
        
        // Return the result
        return ans;
    }

    public boolean isCyclic(int V, List<Integer> adj[]) {
        // To store the topological ordering
        List<Integer> topo = topoSort(V, adj);
        
        /* If topological sort doesn't include all
         nodes, the graph is cyclic in nature */
        if(topo.size() < V) return true;
        
        // Else the graph is acyclic
        return false;
    }

    public static void main(String[] args) {
        int V = 6;
        List<Integer>[] adj = new ArrayList[V];
        for(int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        
        adj[0].add(1);
        adj[1].add(2);
        adj[1].add(5);
        adj[2].add(3);
        adj[3].add(4);
        adj[4].add(1);
        
        // Creating an instance of Solution class
        Solution sol = new Solution();
        
        /* Function call to determine if cycle
         exists in given directed graph */
        boolean ans = sol.isCyclic(V, adj);
        
        // Output
        if(ans)
            System.out.println("The given directed graph contains a cycle.");
        else 
            System.out.println("The given directed graph does not contain a cycle.");
    }
}
from collections import deque

class Solution:
    # Function to return the topological 
    # sorting of given graph
    def topoSort(self, V, adj):
        # To store the result
        ans = []
        
        # To store the In-degrees of nodes
        inDegree = [0] * V
        
        # Calculating the In-degree of the given graph
        for i in range(V):
            for it in adj[i]:
                inDegree[it] += 1
        
        # Queue to facilitate BFS
        q = deque()
        
        # Add the nodes with no in-degree to queue
        for i in range(V):
            if inDegree[i] == 0:
                q.append(i)
        
        # Until the queue is empty
        while q:
            # Get the node
            node = q.popleft()
            
            # Add it to the answer
            ans.append(node)
            
            # Traverse the neighbours
            for it in adj[node]:
                # Decrement the in-degree
                inDegree[it] -= 1
                
                # Add the node to queue if 
                # its in-degree becomes zero
                if inDegree[it] == 0:
                    q.append(it)
        
        # Return the result
        return ans

    # Function to detect cycle in a directed graph.
    def isCyclic(self, V, adj):
        # To store the topological ordering
        topo = self.topoSort(V, adj)
        
        # If topological sort doesn't include all
        # nodes, the graph is cyclic in nature
        if len(topo) < V:
            return True
        
        # Else the graph is acyclic
        return False

if __name__ == "__main__":
    V = 6
    adj = [[] for _ in range(V)]
    
    adj[0].append(1)
    adj[1].extend([2, 5])
    adj[2].append(3)
    adj[3].append(4)
    adj[4].append(1)
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to determine if cycle exists in given directed graph
    ans = sol.isCyclic(V, adj)
    
    # Output
    if ans:
        print("The given directed graph contains a cycle.")
    else:
        print("The given directed graph does not contain a cycle.")
class Solution {
    /* Function to return the topological 
     sorting of given graph */
    topoSort(V, adj) {
        // To store the result
        let ans = [];
        
        // To store the In-degrees of nodes
        let inDegree = new Array(V).fill(0);
        
        /* Calculating the In-degree 
        of the given graph */
        for (let i = 0; i < V; i++) {
            for (let it of adj[i]) {
                inDegree[it]++;
            }
        }
        
        // Queue to facilitate BFS
        let q = [];
        
        // Add the nodes with no in-degree to queue
        for (let i = 0; i < V; i++) {
            if (inDegree[i] === 0) {
                q.push(i);
            }
        }
        
        // Until the queue is empty
        while (q.length > 0) {
            // Get the node
            let node = q.shift();
            
            // Add it to the answer
            ans.push(node);
            
            // Traverse the neighbours
            for (let it of adj[node]) {
                // Decrement the in-degree
                inDegree[it]--;
                
                /* Add the node to queue if its 
                in-degree becomes zero */
                if (inDegree[it] === 0) {
                    q.push(it);
                }
            }
        }
        
        // Return the result
        return ans;
    }

    // Function to detect cycle in a directed graph.
    isCyclic(V, adj) {
        // To store the topological ordering
        let topo = this.topoSort(V, adj);
        
        /* If topological sort doesn't include all 
        nodes, the graph is cyclic in nature */
        if (topo.length < V) {
            return true;
        }
        
        // Else the graph is acyclic
        return false;
    }
}

let V = 6;
let adj = [
    [1],
    [2, 5],
    [3],
    [4],
    [1],
    []
];

// Creating an instance of Solution class
let sol = new Solution();

// Function call to determine if cycle exists in given directed graph
let ans = sol.isCyclic(V, adj);

// Output
if (ans) {
    console.log("The given directed graph contains a cycle.");
} else {
    console.log("The given directed graph does not contain a cycle.");
}

Complexity Analysis:

Time Complexity: O(V+E) (where V and E represent the number of nodes and edges in the graph)
Topological Sort based on BFS (Kahn's Algorithm) takes O(V+E) time.

Space Complexity: O(V)
Array required to store in-degrees takes up O(V) space and queue space will be O(V) in the worst case.

Problem List

Detect a cycle in a directed graph

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code