Detecting a cycle in a directed graph using Depth First Traversal

suggest change

A cycle in a directed graph exists if there’s a back edge discovered during a DFS. A back edge is an edge from a node to itself or one of the ancestors in a DFS tree. For a disconnected graph, we get a DFS forest, so you have to iterate through all vertices in the graph to find disjoint DFS trees.

C++ implementation:

#include <iostream>
 #include <list>
    
using namespace std; 

#define NUM_V   4

bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
{
    visited[u]=true;
    recStack[u]=true;
    list<int>::iterator i;
    for(i = graph[u].begin();i!=graph[u].end();++i)
    {  
        if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
            return true;
        else if(*i==u) //if there's an edge from the vertex to itself
            return true;
        else if(!visited[*i])
        {   if(helper(graph, *i, visited, recStack))
               return true;
        }
    }
    recStack[u]=false;
    return false;
}
/*
/The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
bool isCyclic(list<int> *graph, int V)
{
  bool visited[V];  //array to track vertices already visited
  bool recStack[V]; //array to track vertices in recursion stack of the traversal.

  for(int i = 0;i<V;i++)
   visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

  for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
  {   if(visited[u]==false)
      {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
           return true;
      }
  }
   return false;
}
/*
Driver function
*/
int main()
{
    list<int>* graph = new list<int>[NUM_V];
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(2);
    graph[2].push_back(0);
    graph[2].push_back(3);
    graph[3].push_back(3);
    bool res = isCyclic(graph, NUM_V);
    cout<<res<<endl;
}

Result: As shown below, there are three back edges in the graph. One between vertex 0 and 2; between vertice 0, 1, and 2; and vertex 3. Time complexity of search is O(V+E) where V is the number of vertices and E is the number of edges.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents