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

This is a C++ Program to check whether an undirected 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 UnDirected 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. using namespace std;
  5.  
  6. // Class for an undirected graph
  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[], int parent);
  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
  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.     adj[w].push_back(v); // Add v to w’s list.
  28. }
  29.  
  30. // A recursive function that uses visited[] and parent to detect
  31. // cycle in subgraph reachable from vertex v.
  32. bool Graph::isCyclicUtil(int v, bool visited[], int parent)
  33. {
  34.     // Mark the current node as visited
  35.     visited[v] = true;
  36.  
  37.     // Recur for all the vertices adjacent to this vertex
  38.     list<int>::iterator i;
  39.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  40.     {
  41.         // If an adjacent is not visited, then recur for that adjacent
  42.         if (!visited[*i])
  43.         {
  44.             if (isCyclicUtil(*i, visited, v))
  45.                 return true;
  46.         }
  47.  
  48.         // If an adjacent is visited and not parent of current vertex,
  49.         // then there is a cycle.
  50.         else if (*i != parent)
  51.             return true;
  52.     }
  53.     return false;
  54. }
  55.  
  56. // Returns true if the graph contains a cycle, else false.
  57. bool Graph::isCyclic()
  58. {
  59.     // Mark all the vertices as not visited and not part of recursion
  60.     // stack
  61.     bool *visited = new bool[V];
  62.     for (int i = 0; i < V; i++)
  63.         visited[i] = false;
  64.  
  65.     // Call the recursive helper function to detect cycle in different
  66.     // DFS trees
  67.     for (int u = 0; u < V; u++)
  68.         if (!visited[u]) // Don't recur for u if it is already visited
  69.             if (isCyclicUtil(u, visited, -1))
  70.                 return true;
  71.  
  72.     return false;
  73. }
  74.  
  75. // Driver program to test above functions
  76. int main()
  77. {
  78.     Graph g1(5);
  79.     g1.addEdge(1, 0);
  80.     g1.addEdge(0, 2);
  81.     g1.addEdge(2, 0);
  82.     g1.addEdge(0, 3);
  83.     g1.addEdge(3, 4);
  84.     g1.isCyclic() ? cout << "Undirected Graph isn't a tree\n" : cout
  85.             << "Undirected Graph is a tree\n";
  86.  
  87.     Graph g2(3);
  88.     g2.addEdge(0, 1);
  89.     g2.addEdge(1, 2);
  90.     g2.isCyclic() ? cout << "Undirected Graph isn't a tree\n" : cout
  91.             << "Undirected Graph is a tree\n";
  92.  
  93.     return 0;
  94. }

Output:

$ g++ UndirectedTree.cpp
$ a.out
 
Undirected Graph isn't a tree
Undirected Graph is 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 Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.