C++ Program to Check if a Directed Graph is a Tree or Not using DFS

«
»
This is a C++ Program to check whether an directed graph is tree or not. Graph is tree if it doesn’t contain cycles.

Here is source code of the C++ Program to Check if an Directed Graph is a Tree or Not Using DFS. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include <list>
  3. #include <limits.h>
  4.  
  5. using namespace std;
  6.  
  7. class Graph
  8. {
  9.         int V; // No. of vertices
  10.         list<int> *adj; // Pointer to an array containing adjacency lists
  11.         bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic()
  12.     public:
  13.         Graph(int V); // Constructor
  14.         void addEdge(int v, int w); // to add an edge to graph
  15.         bool isCyclic(); // returns true if there is a cycle in this graph
  16. };
  17.  
  18. Graph::Graph(int V)
  19. {
  20.     this->V = V;
  21.     adj = new list<int> [V];
  22. }
  23.  
  24. void Graph::addEdge(int v, int w)
  25. {
  26.     adj[v].push_back(w); // Add w to v’s list.
  27. }
  28.  
  29. // This function is a variation of DFSUytil() in http://www.geeksforgeeks.org/archives/18212
  30. bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
  31. {
  32.     if (visited[v] == false)
  33.     {
  34.         // Mark the current node as visited and part of recursion stack
  35.         visited[v] = true;
  36.         recStack[v] = true;
  37.  
  38.         // Recur for all the vertices adjacent to this vertex
  39.         list<int>::iterator i;
  40.         for (i = adj[v].begin(); i != adj[v].end(); ++i)
  41.         {
  42.             if (!visited[*i] && isCyclicUtil(*i, visited, recStack))
  43.                 return true;
  44.             else if (recStack[*i])
  45.                 return true;
  46.         }
  47.  
  48.     }
  49.     recStack[v] = false; // remove the vertex from recursion stack
  50.     return false;
  51. }
  52.  
  53. // Returns true if the graph contains a cycle, else false.
  54. // This function is a variation of DFS() in http://www.geeksforgeeks.org/archives/18212
  55. bool Graph::isCyclic()
  56. {
  57.     // Mark all the vertices as not visited and not part of recursion
  58.     // stack
  59.     bool *visited = new bool[V];
  60.     bool *recStack = new bool[V];
  61.     for (int i = 0; i < V; i++)
  62.     {
  63.         visited[i] = false;
  64.         recStack[i] = false;
  65.     }
  66.  
  67.     // Call the recursive helper function to detect cycle in different
  68.     // DFS trees
  69.     for (int i = 0; i < V; i++)
  70.         if (isCyclicUtil(i, visited, recStack))
  71.             return true;
  72.  
  73.     return false;
  74. }
  75.  
  76. int main()
  77. {
  78.     // Create a graph given in the above diagram
  79.     Graph g(4);
  80.     g.addEdge(0, 1);
  81.     g.addEdge(0, 2);
  82.     g.addEdge(1, 2);
  83.     g.addEdge(2, 0);
  84.     g.addEdge(2, 3);
  85.     g.addEdge(3, 3);
  86.  
  87.     if (g.isCyclic())
  88.         cout << "Directed Graph isn't a tree";
  89.     else
  90.         cout << "Directed Graph is a tree";
  91.     return 0;
  92. }

Output:

advertisement
$ g++ DirectedTree.cpp
$ a.out
 
Directed Graph isn't a tree
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.