Menu Close

Detecting a cycle in a directed graph using Depth First Traversal

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 !!



Morae Q!

  1. Convert from binary number to decimal number.
  2. Swap two numbers by using division and multiplication.
  3. Compute foot and inches into centimetres.
  4. Concatenate Strings.
  5. Convert lowercase letters to uppercase letters.
  6. Compute the sum of all the digits of N.
  7. Compute the area of the pentagon.
  8.  Get input using scanner.
  9. Find the distance between two points (x1,y1) and (x2,y2).
  10. Finding patterns in a file using frep and egrep .
  11. Detecting a cycle in a directed graph using Depth First Traversal.
  12. Topological ordering in a Graph.
  13. Storing graphs using adjacency list.
  14. Introduction to graph theory.
  15. Graph Adjacency Matrix pseudo code.
  16. Adjacency Matrix for storing graphs.
  17. Dijkstra’s shortest path algorithm .
  18. Breadth first search (BFS) Algorithm.
  19. Find the multiple of given number in the list of integers.
  20. Finding patterns in files using grep .