Detect cycle in a directed graph using colors

Example 📚

Input: n= 3, e = 4

1 ->2, 1->3, 2->4, 3->2

Output: Yes

Explanation:

This diagram clearly shows no cycle.

Input: n=4,e = 5

1 -> 2, 2->3, 4->2, 2->4, 4->1

Output: yes

Explanation:

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

Algorithm ✍️

🧿Step1: Creating a recursive function that will take the edge and color array

🧿Step2: Label the current node as GREY.

🧿 Step3:Then we need to traverse all the adjacent nodes and return true if any node is marked GREY.

🧿Step4: If any adjacent vertex is WHITE, call the recursive function for that node. If it returns true. Return true.

🧿Step5:If no adjacent node is grey or has not returned true, label the current node as BLACK and return false.

Approach 👩‍💻

• We can see DFS Algorithm to detect cycles in a Graph. 
   
• We can see that there is a cycle in a graph if there is a back edge present in the graph.
   
• The back edge is nothing but a self-loop, which is from a node to itself or one of its ancestors in the tree created by DFS.
   
• We can check cycles in an individual tree by looking for back edges to detect cycles.
   
• The motive is to do DFS of a given graph, and while doing traversal, we need to assign three colors to every vertex. Those three colors are mentioned below: 

Solution📝

🧵C++

#include <bits/stdc++.h>
using namespace std;
 
enum Color {WHITE, GRAY, BLACK};
 
/* Graph class represents a directed graph using
 adjacency list representation */
class Graph1
{
    int Vert; 
    list<int>* adj; 


    bool DFSUtil(int v, int color[]);
public:
    Graph1(int Vert); /* Constructor */
 
   
    void addEdge(int v, int w);
 
    bool isCyclic();
};
 
/* Constructor */
Graph1::Graph1(int Vert)
{
    this->Vert = Vert;
    adj = new list<int>[Vert];
}
 
/* Utility function to add an edge */
void Graph1::addEdge(int v, int w)
{
    adj[v].push_back(w); 
}
 
/* Recursive function to find if there is the back edge
 in the DFS subtree tree rooted with 'u' */
bool Graph1::DFSUtil(int u, int color[])
{
    /* GREY: This vertex is being processed (DFS
             for this vertex has started, but not
             ended (or this vertex is in function
             call stack) */
    color[u] = GREY;
 
    
    list<int>::iterator i;
/* loop */
    for (i = adj[u].begin(); i != adj[u].end(); ++i)
    {
        int v = *i; 
 
        /* If there is */
        if (color[v] == GREY)
          return true;


        if (color[v] == WHITE && DFSUtil(v, color))
          return true;
    }
 


    color[u] = BLACK;
 
    return false;
}


bool Graph1::isCyclic()
{
    /* Initialize the color of all vertices as WHITE */
    int *color = new int[Vert];
    for (int i = 0; i < Vert; i++)
        color[i] = WHITE;
 
    /*Do a DFS traversal beginning with all
     vertices */
    for (int i = 0; i < Vert; i++)
        if (color[i] == WHITE)
           if (DFSUtil(i, color) == true)
              return true;
 
    return false;
}
 


int main()
{


    Graph1 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;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

Graph contains cycle

You can also try this code with Online C++ Compiler

Run Code

Time complexity: The complexity for the above code is O(V + E), where E represents the number of edges and V represents the number of vertices and in the graph.

Space complexity: O(V), as an extra color array is required as of size V.

🧵Java

import java.io.*;
import java.util.*;
 
class CN
{
 
    /* A DFS-based approach to finding if there is a cycle
     in a directed graph. This approach strictly follows
     the algorithm given in the CLRS book.*/
    static int WHITE = 0, GREY = 1, BLACK = 2;
 
    /* Graph class represents a directed graph using
    adjacency list representation */
    static class Graph1
    {
            int Vert;
            LinkedList<Integer>[] adjList;
             
            /* Constructor */
            Graph1(int ver)
            {
                Vert = ver;
                adjList = new LinkedList[V];
                for (int i = 0; i < Vert; i++)
                    adjList[i] = new LinkedList<>();
            }
    }
 
    /* Utility function to add an edge */
    static void addEdge(Graph1 g, int u, int v)
    {
            g.adjList[u].add(v); /* Add v to u's list. */
    }
 
    /* Recursive function to find if there is the back edge
    in DFS subtree tree rooted with 'u' */
    static boolean DFSUtil(Graph1 g, int u, int[] color)
    {
            /* GREY: This vertex is being processed (DFS
             for this vertex has started, but not
             ended (or this vertex is in function
             call stack) */
            color[u] = GREY;
             
            /* Iterate through all adjacent vertices */
            for (Integer in : g.adjList[u])
            {
                /* If there is */
                if (color[in] == GREY)
                    return true;
 
                
                if (color[in] == WHITE && DFSUtil(g, in, color) == true)
                    return true;
            }
 
            
            color[u] = BLACK;
            return false;
    }


    static boolean isCyclic(Graph1 g)
    {
            /* Initialize the color of all vertices as WHITE */
            int[] color = new int[g.Vert];
            for (int i = 0; i < g.Vert; i++)
            {
                color[i] = WHITE;
            }
 
            /* Do a DFS traversal beginning with all
             vertices */
            for (int i = 0; i < g.Vert; i++)
            {
                if (color[i] == WHITE)
                {
                    if(DFSUtil(g, i, color) == true)
                        return true;
                }
            }
            return false;
 
    }
 


    public static void main(String args[])
    {


            Graph1 g = new Graph1(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");
    }
}

You can also try this code with Online Java Compiler

Run Code

Output: 

Graph contains cycle

You can also try this code with Online Java Compiler

Run Code

Time complexity: The complexity for the above code is O(V + E), where E represents the number of edges and V represents the number of vertices and in the graph.

Space complexity: O(V), as an extra color array is required as of size V.

🧵Python

from collections import defaultdict
 
class Graph1():
    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):
        # GREY: 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] == "GREY":
                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
 
g1 = Graph1(4)
g1.addEdge(0, 1)
g1.addEdge(0, 2)
g1.addEdge(1, 2)
g1.addEdge(2, 0)
g1.addEdge(2, 3)
g1.addEdge(3, 3)
print ("Graph contains cycle" if g1.isCyclic() == True\
                             else "Graph doesn't contain cycle")

You can also try this code with Online Python Compiler

Run Code

Output: 

Graph contains cycle

You can also try this code with Online Python Compiler

Run Code

Time complexity: The complexity for the above code is O(V + E), where E represents the number of edges and V represents the number of vertices and in the graph.

Space complexity: O(V), as an extra color array is required as of size V.

Frequently Asked Questions

What is directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

What are cyclic and acyclic graphs?

If a network has a cycle—a continuous set of nodes without any repeating nodes or edges that connect back to itself—it is said to be cyclic. Acyclic graphs are those without cycles.

How do you represent a graph?

Three data structures—the adjacency matrix, adjacency list, and adjacency set—can each be used to represent a graph. One way to see an adjacency matrix is as a table with rows and columns. Row labels and column labels represent the nodes of a graph.

What are weighted and unweighted graphs?

Each edge has a "weight" if a graph is weighted. The weight might, for instance, be used to reflect the trip time or cost and the distance between two locations.

Conclusion

This article taught us how to use colors to detect cycles in a directed graph. We began with a brief introduction to the graphs, followed by an algorithm and detailed code example.

After reading about finding the maximum edges that can be added to a directed acyclic graph so that it remains a directed acyclic graph, refer to Learn Graphs 1- Coding Ninjas, Introduction to Graphs, Learn Graphs 2- Coding Ninjas, and Advanced Graphs for CP or a deeper understanding of graphs.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy learning, Ninja🥷