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.

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:

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:

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📝

🧵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.