Menu Close

Detecting a cycle in a directed graph using Depth First Traversal …FTC

Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Introduction To Graph Theory …FTC 👈 👈 😉

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

Output of the above program is : 1

Illustration of Output of above program in terminal

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.

To store a graph, two methods are common:

  • Adjacency Matrix
  • Adjacency List

An adjacency matrix is a square matrix used to represent a finite graph. Adjacency Matrix (Storing Graphs)  ðŸ‘ˆ 👈 😉 

An Adjacency list is a collection of unordered lists used to represent a finite graph. Storing Graphs (Adjacency List)  ðŸ‘ˆ 👈 😉 

Explore

1. Quantum Mechanics relation with quantum computing

2. Unzipping Files using Python

3. An Algorithm which accepts n integer values and calculates the average and prints it.

4. How can Quantum Computing merge with Virtual Reality ? !

5. Blockchain and Cryptocurrency. And their relations with Virtual Reality !!