C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Check if an Directed Graph is a Tree or Not Using DFS 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. #include<iostream> #include <list> #include <limits.h> using namespace std; class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists bool isCyclicUtil(int v, bool visited[], bool *rs); // used by isCyclic() public: Graph(int V); // Constructor void addEdge(int v, int w); // to add an edge to graph bool isCyclic(); // returns true if there is a cycle in this graph }; Graph::Graph(int V) { this->V = V; adj = new list<int> [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack) { if (visited[v] == false) { // Mark the current node as visited and part of recursion stack visited[v] = true; recStack[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { if (!visited[*i] && isCyclicUtil(*i, visited, recStack)) return true; else if (recStack[*i]) return true; } } recStack[v] = false; // remove the vertex from recursion stack return false; } // Returns true if the graph contains a cycle, else false. bool Graph::isCyclic() { // Mark all the vertices as not visited and not part of recursion stack bool *visited = new bool[V]; bool *recStack = new bool[V]; for (int i = 0; i < V; i++) { visited[i] = false; recStack[i] = false; } // Call the recursive helper function to detect cycle in different DFS trees for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false; } int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); if (g.isCyclic()) cout << "Directed Graph isn't a tree"; else cout << "Directed Graph is a tree"; return 0; }