# Detecting cycle in directed graphs using Depth-First-Search (DFS)

• Cycle in directed graphs can be detected easily using a depth-first search traversal.
• Idea
While doing a depth-first search traversal, we keep track of the nodes visited in the current traversal path in addition to the list of all the visited nodes. During the traversal of the current path, if we come to a node that was already marked visited then we have found a cycle.

Algorithm : Detect_Cycle ( Node source_node )

1.    Mark the source_node as visited.
2.    Mark the source_node as in_path node.
3.    For all the adjacent nodes to the source_node do
4.        If the adjacent node has been marked as in_path node, then
5.            Cycle found. Return.
6.        If the adjacent node has not been visited, then
8.    Now that we are backtracking unmark the source_node in in_path as it might be revisited.

Example Time complexity : O ( E + V ). This algorithm uses a depth-first search traversal for traversing all the nodes in the graph. As the graph is stored in an adjacency list, the neighbors of a vertex on the outgoing edge are explored successively/linearly. As each vertex is explored only once, all the vertices are explored in O ( V ) time. The total number of edges (maintained in the adjacency list) are E for a directed graph. Thus the time complexity is O ( E + V ) for a directed graph.

Program for detecting cycle in a directed graph

``````from collections import defaultdict

class Graph:

def __init__(self, nodes : int):
# The default dictionary would create an empty list as a default (value)
# for the nonexistent keys.
self.nodes = nodes
self.visited = [False] * nodes
# inpath stores the visited nodes in the traversal path
# for finding cycle in a directed graph.
self.inpath = [False] * nodes
self.cycle_present = False

def AddEdge (self, src : int, dst : int, bidirectional : bool):

if bidirectional: # Check if the edge is undirected (bidirectional)

# Function detects cycle in a directed graph using
# DFS technique at its core.
def DetectCycle (self, src : int):

self.visited[src] = True

# Set the flag for the vertex visited in traversal path
self.inpath[src] = True

self.cycle_present = True
return

# Before we backtrack unset the flag for the src vertex as it
# might be in the next traversal path
self.inpath[src] = False

# Mark nodes unvisited for the next traversal
def MarkUnvisited (self):
self.visited = [False] * nodes

def CyclePresent (self):
return self.cycle_present

def main():

nodes = 7
g1_directed = Graph(nodes)

#  Graph 1
#  6-----------
#  ^          |
#  |          |
#  4<------5<--
#  ^       ^
#  |       |
#  1<------3
#  ^       ^
#  |       |
#  0 ----->2

# Add edges to the directed graph

g1_directed.DetectCycle(0)

if g1_directed.CyclePresent() == True:
print("Cycle found in the directed graph g1")
else:

# Graph 2
# 4-
# ^ \
# |  \
# 3   \
# ^    \
# |     \
# 2      \
# ^       \
# |        \
# 0--->1<---

nodes = 5
g2_directed = Graph(nodes)

g2_directed.DetectCycle(0)

if g2_directed.CyclePresent() == True:
print("Cycle found in the directed graph g2")
else:

if __name__ == "__main__":
main()
``````

Output

``````Cycle found in the directed graph g1
``````
``````#include<iostream>
#include<list>
#include<vector>
#include<stack>

using namespace std;

class Graph {

private:

int nodes;
vector<bool> visited;

// inpath stores the visited nodes in the traversal path before backtracking
// for finding cycle in a directed graph.
vector<bool> inpath;

bool cycle_present;

public:

Graph() {
}

Graph (int arg_nodes) {

this->nodes = arg_nodes;
visited.resize(nodes, false);
inpath.resize(nodes, false);
cycle_present = false;
}

~Graph () {
}

void AddEdge (int src, int dst, bool bidirectional) {

if (bidirectional)
}

// Function detects cycle in a directed graph
// using DFS technique at its core
void DetectCycle (int src) {

visited[src] = true;
// Set the flag for the vertex visited in traversal path
//
inpath[src] = true;

cycle_present = true;
return;
}
}
// Before we backtrack unset the flag for the src vertex as it will
// not be in the next traversal path
inpath[src] = false;
}

// Mark nodes unvisited for the next traversal
void MarkUnvisited () {
fill(visited.begin(), visited.end(), false);
}

bool CyclePresent() {
return cycle_present;
}
};

int main()
{
Graph g1_directed (7);

/*
Graph 1
6-----------
^          |
|          |
4<------5<--
^       ^
|       |
1<------3
^       ^
|       |
0 ----->2 */

// Add edges to the directed graph

g1_directed.DetectCycle(0);

if (g1_directed.CyclePresent()) {
cout << "Cycle found in the directed graph g1" << endl;
} else {
cout << "Cycle not found in the directed graph g1" << endl;
}

Graph g2_directed (5);
/*
Graph 2
4-
^ \
|  \
3   \
^    \
|     \
2      \
^       \
|        \
0--->1<---
*/

g2_directed.DetectCycle(0);

if (g2_directed.CyclePresent()) {
cout << "Cycle found in the directed graph g2" << endl;
} else {
cout << "Cycle not found in the directed graph g2" << endl;
}
return 0;
}
``````

Output

``````Cycle found in the directed graph g1
``````
``````import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Graph {

private int nodes;
private boolean visited[];

// inpath stores the visited nodes in the traversal path before backtracking
// for finding cycle in a directed graph.
private boolean inpath[];

boolean cycle_present;

Graph (int arg_nodes) {

nodes = arg_nodes;

for(int i=0; i<nodes; i++) {
}

visited = new boolean[nodes];
inpath  = new boolean[nodes];

cycle_present = false;
}

public void AddEdge (int src, int dst, boolean bidirectional) {

if (bidirectional)
}

// Function detects cycle in a directed graph
// using DFS technique at its core.
public void DetectCycle (int src) {

visited[src] = true;
// Set the flag for the vertex visited in traversal path
//
inpath[src] = true;

cycle_present = true;
return;
}
}
// Before we backtrack unset the flag for the src vertex as it will
// not be in the next traversal path
inpath[src] = false;
}

// Mark nodes unvisited for the next traversal
public void MarkUnvisited () {
Arrays.fill(visited, false);
}

public boolean CyclePresent() {
return cycle_present;
}

public static void main (String[] args) {

Graph g1_directed = new Graph(7);
/*
Graph 1
6-----------
^          |
|          |
4<------5<--
^       ^
|       |
1<------3
^       ^
|       |
0 ----->2 */

// Add edges to the directed graph

g1_directed.DetectCycle(0);

if (g1_directed.CyclePresent()) {
System.out.println("Cycle found in the directed graph g1");
} else {
}

Graph g2_directed = new Graph(5);

/*
Graph 2
4-
^ \
|  \
3   \
^    \
|     \
2      \
^       \
|        \
0--->1<---
*/

g2_directed.DetectCycle(0);

if (g2_directed.CyclePresent()) {
System.out.println("Cycle found in the directed graph g2");
} else {
}
}
}
``````

Output

``````Cycle found in the directed graph g1