C++ Program to Check if an 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.

advertisement
advertisement

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter