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:

advertisement
$ 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 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