C++ Program to Check whether Undirected Graph is Connected 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
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