Detect Cycle in a directed graph using colors

Last Updated : 30 Jun, 2022

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.

Example:

Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: Yes
Explanation:

This diagram clearly shows a cycle 0 -> 2 -> 0.

Input:n = 4, e = 3
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3
Output:No
Explanation:

This diagram clearly shows no cycle.

Solution
Approach: Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. It can be observed that these 3 back edges indicate 3 cycles present in the graph.

Depth First Traversal to detect cycle in a Graph

For a disconnected graph, we get the DFS forest as output. To detect cycle, we can check for cycle in individual trees by checking back edges.

In the previous post, we have discussed a solution that stores visited vertices in a separate array which stores vertices of the current recursion call stack.

In this post, a different solution is discussed. The solution is from CLRS book. The idea is to do DFS of a given graph and while doing traversal, assign one of the below three colours to every vertex.

WHITE : Vertex is not processed yet. Initially, all vertices are WHITE.
GRAY: Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (in DFS tree) of this vertex are not processed yet (or this vertex is in the function call stack)
BLACK : Vertex and all its descendants are processed. While doing DFS, if an edge is encountered from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle.

Algorithm:

Create a recursive function that takes the edge and color array (this can be also kept as a global variable)

Mark the current node as GREY.

Traverse all the adjacent nodes and if any node is marked GREY then return true as a loop is bound to exist.

If any adjacent vertex is WHITE then call the recursive function for that node. If the function returns true. Return true.

If no adjacent node is grey or has not returned true then mark the current Node as BLACK and return false.

Implementation:

C++

// A DFS based approach to find if there is a cycle
// in a directed graph.  This approach strictly follows
// the algorithm given in CLRS book.
#include <bits/stdc++.h>
using namespace std;
 
enum Color {WHITE, GRAY, BLACK};
 
// Graph class represents a directed graph using
// adjacency list representation
class Graph
{
    int V; // No. of vertices
    list<int>* adj; // adjacency lists
 
    // DFS traversal of the vertices reachable from v
    bool DFSUtil(int v, int color[]);
public:
    Graph(int V);  // Constructor
 
    // function to add an edge to graph
    void addEdge(int v, int w);
 
    bool isCyclic();
};
 
// Constructor
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
// Utility function to add an edge
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v's list.
}
 
// Recursive function to find if there is back edge
// in DFS subtree tree rooted with 'u'
bool Graph::DFSUtil(int u, int color[])
{
    // GRAY :  This vertex is being processed (DFS
    //         for this vertex has started, but not
    //         ended (or this vertex is in function
    //         call stack)
    color[u] = GRAY;
 
    // Iterate through all adjacent vertices
    list<int>::iterator i;
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i;  // An adjacent of u
 
        // If there is
        if (color[v] == GRAY)
          return true;
 
        // If v is not processed and there is a back
        // edge in subtree rooted with v
        if (color[v] == WHITE && DFSUtil(v, color))
          return true;
    }
 
    // Mark this vertex as processed
    color[u] = BLACK;
 
    return false;
}
 
// Returns true if there is a cycle in graph
bool Graph::isCyclic()
{
    // Initialize color of all vertices as WHITE
    int *color = new int[V];
    for (int i = 0; i < V; i++)
        color[i] = WHITE;
 
    // Do a DFS traversal beginning with all
    // vertices
    for (int i = 0; i < V; i++)
        if (color[i] == WHITE)
           if (DFSUtil(i, color) == true)
              return true;
 
    return false;
}
 
// Driver code to test above
int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 
    if (g.isCyclic())
        cout << "Graph contains cycle";
    else
        cout << "Graph doesn't contain cycle";
 
    return 0;
}

Java

import java.io.*;
import java.util.*;
 
class GFG 
{
 
    // A DFS based approach to find if there is a cycle 
    // in a directed graph. This approach strictly follows 
    // the algorithm given in CLRS book. 
    static int WHITE = 0, GRAY = 1, BLACK = 2;
 
    // Graph class represents a directed graph using 
    // adjacency list representation 
    static class Graph 
    {
            int V;
            LinkedList<Integer>[] adjList;
             
            // Constructor 
            Graph(int ver)
            {
                V = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < V; i++)
                    adjList[i] = new LinkedList<>();
            }
    }
 
    // Utility function to add an edge 
    static void addEdge(Graph g, int u, int v)
    {
            g.adjList[u].add(v); // Add v to u's list. 
    }
 
    // Recursive function to find if there is back edge 
    // in DFS subtree tree rooted with 'u' 
    static boolean DFSUtil(Graph g, int u, int[] color) 
    {
            // GRAY : This vertex is being processed (DFS 
            // for this vertex has started, but not 
            // ended (or this vertex is in function 
            // call stack) 
            color[u] = GRAY;
             
            // Iterate through all adjacent vertices
            for (Integer in : g.adjList[u]) 
            {
                // If there is
                if (color[in] == GRAY)
                    return true;
 
                // If v is not processed and there is a back 
                // edge in subtree rooted with v 
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }
 
            // Mark this vertex as processed 
            color[u] = BLACK;
            return false;
    }
 
    // Returns true if there is a cycle in graph
    static boolean isCyclic(Graph g)
    {
            // Initialize color of all vertices as WHITE
            int[] color = new int[g.V];
            for (int i = 0; i < g.V; i++)
            {
                color[i] = WHITE;
            }
 
            // Do a DFS traversal beginning with all 
            // vertices 
            for (int i = 0; i < g.V; i++) 
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true) 
                        return true;
                } 
            }
            return false;
 
    }
 
    // Driver code to test above
    public static void main(String args[])
    {
            // Create a graph given in the above diagram
            Graph g = new Graph(4);
            addEdge(g, 0, 1);
            addEdge(g, 0, 2);
            addEdge(g, 1, 2);
            addEdge(g, 2, 0);
            addEdge(g, 2, 3);
            addEdge(g, 3, 3);
            if (isCyclic(g))
                System.out.println("Graph contains cycle");
            else
                System.out.println("Graph doesn't contain cycle");
    }
}
 
// This code is contributed by rachana soma 

Python3

# Python program to detect cycle in 
# a directed graph
 
from collections import defaultdict
 
class Graph():
    def __init__(self, V):
        self.V = V
        self.graph = defaultdict(list)
 
    def addEdge(self, u, v):
        self.graph[u].append(v)
 
    def DFSUtil(self, u, color):
        # GRAY :  This vertex is being processed (DFS
        #         for this vertex has started, but not
        #         ended (or this vertex is in function
        #         call stack)
        color[u] = "GRAY"
 
        for v in self.graph[u]:
 
            if color[v] == "GRAY":
                return True
 
            if color[v] == "WHITE" and self.DFSUtil(v, color) == True:
                return True
 
        color[u] = "BLACK"
        return False
 
    def isCyclic(self):
        color = ["WHITE"] * self.V
 
        for i in range(self.V):
            if color[i] == "WHITE":
                if self.DFSUtil(i, color) == True:
                    return True
        return False
 
# Driver program to test above functions
 
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Graph contains cycle" if g.isCyclic() == True\
                             else "Graph doesn't contain cycle")
                              
# This program is contributed by Divyanshu Mehta                             

C#

// A C# program to detect cycle in
// an undirected graph using BFS.
using System;
using System.Collections.Generic;
 
class GFG 
{
 
    // A DFS based approach to find if 
    // there is a cycle in a directed graph. 
    // This approach strictly follows the 
    // algorithm given in CLRS book. 
    static int WHITE = 0, GRAY = 1, BLACK = 2;
 
    // Graph class represents a directed graph 
    // using adjacency list representation 
    public class Graph 
    {
        public int V;
        public List<int>[] adjList;
         
        // Constructor 
        public Graph(int ver)
        {
            V = ver;
            adjList = new List<int>[V];
            for (int i = 0; i < V; i++)
                adjList[i] = new List<int>();
        }
    }
 
    // Utility function to add an edge 
    static void addEdge(Graph g, int u, int v)
    {
        g.adjList[u].Add(v); // Add v to u's list. 
    }
 
    // Recursive function to find if there is back edge 
    // in DFS subtree tree rooted with 'u' 
    static bool DFSUtil(Graph g, int u, int[] color) 
    {
        // GRAY : This vertex is being processed (DFS 
        // for this vertex has started, but not 
        // ended (or this vertex is in function 
        // call stack) 
        color[u] = GRAY;
         
        // Iterate through all adjacent vertices
        foreach (int iN in g.adjList[u]) 
        {
            // If there is
            if (color[iN] == GRAY)
                return true;
 
            // If v is not processed and there is a back 
            // edge in subtree rooted with v 
            if (color[iN] == WHITE && 
                DFSUtil(g, iN, color) == true)
                return true;
        }
 
        // Mark this vertex as processed 
        color[u] = BLACK;
        return false;
    }
     
    // Returns true if there is a cycle in graph
    static bool isCyclic(Graph g)
    {
        // Initialize color of all vertices as WHITE
        int[] color = new int[g.V];
        for (int i = 0; i < g.V; i++)
        {
            color[i] = WHITE;
        }
 
        // Do a DFS traversal beginning with all 
        // vertices 
        for (int i = 0; i < g.V; i++) 
        {
            if (color[i] == WHITE)
            {
                if(DFSUtil(g, i, color) == true) 
                    return true;
            } 
        }
        return false;
 
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        // Create a graph given in the above diagram
        Graph g = new Graph(4);
        addEdge(g, 0, 1);
        addEdge(g, 0, 2);
        addEdge(g, 1, 2);
        addEdge(g, 2, 0);
        addEdge(g, 2, 3);
        addEdge(g, 3, 3);
        if (isCyclic(g))
            Console.WriteLine("Graph contains cycle");
        else
            Console.WriteLine("Graph doesn't contain cycle");
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// A Javascript program to detect cycle in
// an undirected graph using BFS.
 
// A DFS based approach to find if 
// there is a cycle in a directed graph. 
// This approach strictly follows the 
// algorithm given in CLRS book. 
var WHITE = 0, GRAY = 1, BLACK = 2;
 
// Graph class represents a directed graph 
// using adjacency list representation 
class Graph 
{
     
    // Constructor 
    constructor(ver)
    {
        this.V = ver;
        this.adjList = Array.from(
            Array(this.V), () => Array(this.V));
    }
}
 
// Utility function to add an edge 
function addEdge(g, u, v)
{
     
    // Push v to u's list. 
    g.adjList[u].push(v); 
}
 
// Recursive function to find if there is back edge 
// in DFS subtree tree rooted with 'u' 
function DFSUtil(g, u, color) 
{
     
    // GRAY : This vertex is being processed (DFS 
    // for this vertex has started, but not 
    // ended (or this vertex is in function 
    // call stack) 
    color[u] = GRAY;
     
    // Iterate through all adjacent vertices
    for(var iN of g.adjList[u]) 
    {
         
        // If there is
        if (color[iN] == GRAY)
            return true;
             
        // If v is not processed and there is a back 
        // edge in subtree rooted with v 
        if (color[iN] == WHITE && 
            DFSUtil(g, iN, color) == true)
            return true;
    }
     
    // Mark this vertex as processed 
    color[u] = BLACK;
    return false;
}
 
// Returns true if there is a cycle in graph
function isCyclic(g)
{
     
    // Initialize color of all vertices as WHITE
    var color =  Array(g.V);
    for(var i = 0; i < g.V; i++)
    {
        color[i] = WHITE;
    }
     
    // Do a DFS traversal beginning with all 
    // vertices 
    for(var i = 0; i < g.V; i++) 
    {
        if (color[i] == WHITE)
        {
            if (DFSUtil(g, i, color) == true) 
                return true;
        } 
    }
    return false;
}
 
// Driver Code
 
// Create a graph given in the above diagram
var g = new Graph(4);
addEdge(g, 0, 1);
addEdge(g, 0, 2);
addEdge(g, 1, 2);
addEdge(g, 2, 0);
addEdge(g, 2, 3);
addEdge(g, 3, 3);
 
if (isCyclic(g))
    document.write("Graph contains cycle");
else
    document.write("Graph doesn't contain cycle");
     
// This code is contributed by rrrtnx
 
</script>

Output

Graph contains cycle

Complexity Analysis:

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity :O(V).
Since an extra color array is needed of size V.

A

Aditya Goel

Improve

Previous Article

Detect cycle in an undirected graph

Detect a negative cycle in a Graph | (Bellman Ford)

Similar Reads

Detect cycle in Directed Graph using Topological Sort

Given a Directed Graph consisting of N vertices and M edges and a set of Edges[][], the task is to check whether the graph contains a cycle or not using Topological sort. Topological sort of directed graph is a linear ordering of its vertices such that, for every directed edge U -> V from vertex U to vertex V, U comes before V in the ordering. E

Detect Cycle in a Directed Graph using BFS

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains two cycles 0->1->2->3->0 and 2->4->2, so your function must return true. Recommended: Please solve it on "PRACTICE" f

Detect Cycle in a Directed Graph

Given the root of a Directed graph , The task is to check whether the graph contains a cycle or not. Examples: Input: N = 4, E = 6 Output: Yes Explanation: The diagram clearly shows a cycle 0 -> 2 -> 0 Input: N = 4, E = 4 Output: No Explanation: The diagram clearly shows no cycle. Recommended Practice Detect cycle in a directed graph Try It!

What is Directed Graph? | Directed Graph meaning

A directed graph is defined as a type of graph where the edges have a direction associated with them. Characteristics of Directed Graph Directed graphs have several characteristics that make them different from undirected graphs. Here are some key characteristics of directed graphs: Directed edges: In a directed graph, edges have a direction associ

Detect cycle in the graph using degrees of nodes of graph

Given a graph, the task is to detect a cycle in the graph using degrees of the nodes in the graph and print all the nodes that are involved in any of the cycles. If there is no cycle in the graph then print -1. Examples: Input: Output: 0 1 2 Approach: Recursively remove all vertices of degree 1. This can be done efficiently by storing a map of vert

Detect a negative cycle in a Graph using Shortest Path Faster Algorithm

Given a graph G consisting of nodes valued [0, N - 1], a source S, and an array Edges[][3] of type {u, v, w} that denotes that there is a directed edge between node u and v with weight w, the task is to check if there exists a negative cycle from the given source. If found to be true, then print "Yes". Otherwise, print "No". A negative cycle is a c

Detect Cycle in Graph using DSU

Given an undirected graph, the task is to check if the graph contains a cycle or not, using DSU. Examples: Input: The following is the graph Output: YesExplanation: There is a cycle of vertices {0, 1, 2}. Recommended PracticeDetect Cycle using DSUTry It!We already have discussed an algorithm to detect cycle in directed graph. Here Union-Find Algori

Detect cycle in an undirected graph using BFS

Given an undirected graph, how to check if there is a cycle in the graph? For example, the following graph has a cycle of 1-0-2-1. Recommended: Please solve it on "PRACTICE" first, before moving on to the solution.We have discussed cycle detection for the directed graph. We have also discussed a union-find algorithm for cycle detection in undirect

Print negative weight cycle in a Directed Graph

Given a weighted directed graph consisting of V vertices and E edges. The task is to print the cyclic path whose sum of weight is negative. If there is no such path present then print "-1". Input: V = 5, E = 5, Below is the graph: Here, for the given negative cycle o/p (1->2->3->4->1) ; In fig there has to be Edge from 4-->1 not from

Print Nodes which are not part of any cycle in a Directed Graph

Given a directed graph G N nodes and E Edges consisting of nodes valued [0, N – 1] and a 2D array Edges[][2] of type {u, v} that denotes a directed edge between vertices u and v. The task is to find the nodes that are not part of any cycle in the given graph G. Examples: Input: N = 4, E = 4, Edges[][2] = { {0, 2}, {0, 1}, {2, 3}, {3, 0} }Output: 1E

Article Tags :

Practice Tags :