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

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

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

advertisement
$ g++ undirected_connected_bfs.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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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.