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

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 7. Detect_Cycle ( adjacent_node ) 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

Python C++ Java

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.adjlist = defaultdict(list)  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):   self.adjlist[src].append(dst)   if bidirectional: # Check if the edge is undirected (bidirectional)  self.adjlist[dst].append(src)   # 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   for adj_node in self.adjlist[src]:   if self.inpath[adj_node] == True:  self.cycle_present = True  return  elif self.visited[adj_node] == False:  self.DetectCycle (adj_node)   # 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   # ^ ^  # | |  # 1  # ^ ^  # | |  # 0 ----->2   # Add edges to the directed graph  g1_directed.AddEdge(0, 1, False)  g1_directed.AddEdge(0, 2, False)  g1_directed.AddEdge(1, 4, False)  g1_directed.AddEdge(2, 3, False)  g1_directed.AddEdge(3, 1, False)  g1_directed.AddEdge(3, 5, False)  g1_directed.AddEdge(4, 6, False)  g1_directed.AddEdge(5, 4, False)  g1_directed.AddEdge(6, 5, False)   g1_directed.DetectCycle(0)   if g1_directed.CyclePresent() == True:  print("Cycle found in the directed graph g1")  else:  print("Cycle not found in the directed graph g1")   # Graph 2  # 4-  # ^ \  # | \  # 3 \  # ^ \  # | \  # 2 \  # ^ \  # | \  # 0--->1   nodes = 5  g2_directed = Graph(nodes)   g2_directed.AddEdge(0, 1, False)  g2_directed.AddEdge(0, 2, False)  g2_directed.AddEdge(2, 3, False)  g2_directed.AddEdge(3, 4, False)  g2_directed.AddEdge(4, 1, False)   g2_directed.DetectCycle(0)   if g2_directed.CyclePresent() == True:  print("Cycle found in the directed graph g2")  else:  print("Cycle not found in the directed graph g2")  if __name__ == "__main__":  main()

Cycle found in the directed graph g1 Cycle not found in the directed graph g2

#include #include #include #include  using namespace std;  class Graph    private:   int nodes;  listint> *adjlist;  vectorbool> visited;   // inpath stores the visited nodes in the traversal path before backtracking  // for finding cycle in a directed graph.  vectorbool> inpath;   bool cycle_present;   public:   Graph()   >   Graph (int arg_nodes)    this->nodes = arg_nodes;  adjlist = new listint> [nodes];  visited.resize(nodes, false);  inpath.resize(nodes, false);  cycle_present = false;  >   ~Graph ()   delete [] adjlist;  >   void AddEdge (int src, int dst, bool bidirectional)    adjlist[src].push_back(dst);   if (bidirectional)  adjlist[dst].push_back(src);  >   // 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;   for (auto& adj_node : adjlist[src])    if (inpath[adj_node])   cycle_present = true;  return;  > else if (!visited[adj_node])   DetectCycle (adj_node);  >  >  // 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  ^ ^  | |  1  ^ ^  | |  0 ----->2 */   // Add edges to the directed graph  g1_directed.AddEdge(0, 1, false);  g1_directed.AddEdge(0, 2, false);  g1_directed.AddEdge(1, 4, false);  g1_directed.AddEdge(2, 3, false);  g1_directed.AddEdge(3, 1, false);  g1_directed.AddEdge(3, 5, false);  g1_directed.AddEdge(4, 6, false);  g1_directed.AddEdge(5, 4, false);  g1_directed.AddEdge(6, 5, false);   g1_directed.DetectCycle(0);   if (g1_directed.CyclePresent())   cout  <"Cycle found in the directed graph g1"    > else   cout  <"Cycle not found in the directed graph g1"    >   Graph g2_directed (5);  /*  Graph 2  4-  ^ \  | \  3 \  ^ \  | \  2 \  ^ \  | \  0--->1  */  g2_directed.AddEdge(0, 1, false);  g2_directed.AddEdge(0, 2, false);  g2_directed.AddEdge(2, 3, false);  g2_directed.AddEdge(3, 4, false);  g2_directed.AddEdge(4, 1, false);   g2_directed.DetectCycle(0);   if (g2_directed.CyclePresent())   cout  <"Cycle found in the directed graph g2"    > else   cout  <"Cycle not found in the directed graph g2"    >  return 0; >

Cycle found in the directed graph g1 Cycle not found in the directed graph g2

import java.util.Arrays; import java.util.ArrayList; import java.util.List;  class Graph    private int nodes;  private ListListInteger>> adjlist;  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;   adjlist = new ArrayList<> (nodes);  for(int i=0; inodes; i++)   adjlist.add(new ArrayList<>());  >   visited = new boolean[nodes];  inpath = new boolean[nodes];   cycle_present = false;  >   public void AddEdge (int src, int dst, boolean bidirectional)    adjlist.get(src).add(dst);   if (bidirectional)  adjlist.get(dst).add(src);  >   // 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;   for (int adj_node : adjlist.get(src))    if (inpath[adj_node])   cycle_present = true;  return;  > else if (!visited[adj_node])   DetectCycle (adj_node);  >  >  // 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  ^ ^  | |  1  ^ ^  | |  0 ----->2 */   // Add edges to the directed graph  g1_directed.AddEdge(0, 1, false);  g1_directed.AddEdge(0, 2, false);  g1_directed.AddEdge(1, 4, false);  g1_directed.AddEdge(2, 3, false);  g1_directed.AddEdge(3, 1, false);  g1_directed.AddEdge(3, 5, false);  g1_directed.AddEdge(4, 6, false);  g1_directed.AddEdge(5, 4, false);  g1_directed.AddEdge(6, 5, false);   g1_directed.DetectCycle(0);   if (g1_directed.CyclePresent())   System.out.println("Cycle found in the directed graph g1");  > else   System.out.println("Cycle not found in the directed graph g1");  >   Graph g2_directed = new Graph(5);   /*  Graph 2  4-  ^ \  | \  3 \  ^ \  | \  2 \  ^ \  | \  0--->1  */  g2_directed.AddEdge(0, 1, false);  g2_directed.AddEdge(0, 2, false);  g2_directed.AddEdge(2, 3, false);  g2_directed.AddEdge(3, 4, false);  g2_directed.AddEdge(4, 1, false);   g2_directed.DetectCycle(0);   if (g2_directed.CyclePresent())   System.out.println("Cycle found in the directed graph g2");  > else   System.out.println("Cycle not found in the directed graph g2");  >  > >

Cycle found in the directed graph g1 Cycle not found in the directed graph g2