C++ Program to Check the Connectivity of Undirected Graph using DFS

«
»
This C++ Program checks whether Undirected Graph is Connected using DFS.

Here is source code of the C++ Program to check whether Undirected Graph is Connected using DFS. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Check whether Undirected Graph is Connected using DFS
  3.  */
  4. #include <iostream>
  5. #include <list>
  6. #include <stack>
  7. using namespace std;
  8. /*
  9.  * Class Declaration
  10.  */
  11. class Graph
  12. {
  13.     private:
  14.         int V;
  15.         list<int> *adj;
  16.         void DFSUtil(int v, bool visited[]);
  17.     public:
  18.         Graph(int V)
  19.         {
  20.             this->V = V;
  21.             adj = new list<int>[V];
  22.         }
  23.         ~Graph()
  24.         {
  25.             delete [] adj;
  26.         }
  27.         void addEdge(int v, int w);
  28.         bool isConnected();
  29.         Graph getTranspose();
  30. };
  31.  
  32. /*
  33.  *  A recursive function to print DFS starting from v
  34.  */
  35. void Graph::DFSUtil(int v, bool visited[])
  36. {
  37.     visited[v] = true;
  38.     list<int>::iterator i;
  39.     for (i = adj[v].begin(); i != adj[v].end(); ++i)
  40.         if (!visited[*i])
  41.             DFSUtil(*i, visited);
  42. }
  43.  
  44. /*
  45.  * Function that returns reverse (or transpose) of this graph
  46.  */
  47. Graph Graph::getTranspose()
  48. {
  49.     Graph g(V);
  50.     for (int v = 0; v < V; v++)
  51.     {
  52.         list<int>::iterator i;
  53.         for(i = adj[v].begin(); i != adj[v].end(); ++i)
  54.         {
  55.             g.adj[*i].push_back(v);
  56.         }
  57.     }
  58.     return g;
  59. }
  60. /*
  61.  * Add Edge to connect v and w
  62.  */
  63. void Graph::addEdge(int v, int w)
  64. {
  65.     adj[v].push_back(w);
  66.     adj[w].push_back(v);
  67. }
  68.  
  69. /*
  70.  * Check if Graph is Connected
  71.  */
  72. bool Graph::isConnected()
  73. {
  74.     bool visited[V];
  75.     for (int i = 0; i < V; i++)
  76.         visited[i] = false;
  77.     DFSUtil(0, visited);
  78.     for (int i = 0; i < V; i++)
  79.         if (visited[i] == false)
  80.              return false;
  81.     Graph gr = getTranspose();
  82.     for(int i = 0; i < V; i++)
  83.         visited[i] = false;
  84.     gr.DFSUtil(0, visited);
  85.     for (int i = 0; i < V; i++)
  86.         if (visited[i] == false)
  87.              return false;
  88.     return true;
  89. }
  90. /*
  91.  * Main Contains Menu
  92.  */
  93. int main()
  94. {
  95.     Graph g1(5);
  96.     g1.addEdge(0, 1);
  97.     g1.addEdge(1, 2);
  98.     g1.addEdge(2, 3);
  99.     g1.addEdge(3, 0);
  100.     g1.addEdge(2, 4);
  101.     g1.addEdge(4, 2);
  102.     if (g1.isConnected())
  103.         cout<<"The Graph is Conneted"<<endl;
  104.     else
  105.         cout<<"The Graph is not Connected"<<endl;
  106.  
  107.     Graph g2(4);
  108.     g2.addEdge(0, 1);
  109.     g2.addEdge(1, 2);
  110.     g2.addEdge(2, 3);
  111.     if (g2.isConnected())
  112.         cout<<"The Graph is Connected"<<endl;
  113.     else
  114.         cout<<"The Graph is not Connected"<<endl;
  115.  
  116.     return 0;
  117. }

advertisement
$ g++ undirected_connected_dfs.cpp
$ a.out
The Graph is Connected
The Graph is Connected
 
------------------
(program exited with code: 0)
Press return to continue

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

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

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.