Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction📘
2.
Problem Statement🎯
3.
Example 📚
4.
Algorithm ✍️
5.
Approach 👩‍💻
6.
Solution📝
6.1.
🧵C++
6.2.
🧵Java
6.3.
🧵Python
7.
Frequently Asked Questions
7.1.
What is directed and undirected graphs?
7.2.
What are cyclic and acyclic graphs?
7.3.
How do you represent a graph?
7.4.
What are weighted and unweighted graphs?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Detect cycle in a directed graph using colors

Author yuvatimankar
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction📘

In graph theory, a directed graph is made from a set of vertices joined by directed edges, also sometimes called arcs. So let's start the article and find out how to detect the cycle in a directed graph using colors.

Detect cycle in a directed graph using colors

Stay till the end!

Problem Statement🎯

We have given a directed graph; we have to check whether the graph contains a cycle or not. The function made should return true if the given graph contains at least one cycle; else, it returns false.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example 📚

Input: n= 3, e = 4

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

Output: Yes

Explanation:

Diag 1

This diagram clearly shows no cycle.

Input: n=4,e = 5

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

Output: yes

Explanation:

diag 2


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

Algorithm ✍️

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 👩‍💻

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: 
WHITE White indicates that the vertex is not processed yet. By default, all vertex are WHITE.
BLACK This color BLACK indicates that the vertex and all its descendants are processed. During DFS, if an edge is met from the current vertex to a GRAY vertex, then this edge is said to be the back edge, and hence there is a cycle.
GREY This indicates that the vertex has started but is not finished. 

Solution📝

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


Output: 

Graph contains cycle


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");
    }
}


Output: 

Graph contains cycle


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")


Output: 

Graph contains cycle


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 NinjasIntroduction to GraphsLearn 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🥷

Previous article
Karp’s Minimum Mean (or Average) Weight Cycle Algorithm
Next article
Check if a Graph has a Cycle of Odd Length
Live masterclass