C++ Program to Check whether Undirected Graph is Connected 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.

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

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