C++ Program to Check whether Directed Graph is Connected using BFS

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

Here is source code of the C++ Program to check whether Directed 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 Directed 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. }
  67. /*
  68.  * Check if Graph is Connected
  69.  */
  70. bool Graph::isConnected()
  71. {
  72.     bool visited[V];
  73.     for (int i = 0; i < V; i++)
  74.         visited[i] = false;
  75.     DFSUtil(0, visited);
  76.     for (int i = 0; i < V; i++)
  77.         if (visited[i] == false)
  78.              return false;
  79.     Graph gr = getTranspose();
  80.     for(int i = 0; i < V; i++)
  81.         visited[i] = false;
  82.     gr.DFSUtil(0, visited);
  83.     for (int i = 0; i < V; i++)
  84.         if (visited[i] == false)
  85.              return false;
  86.     return true;
  87. }
  88. /*
  89.  * Main Contains Menu
  90.  */
  91. int main()
  92. {
  93.     Graph g1(5);
  94.     g1.addEdge(0, 1);
  95.     g1.addEdge(1, 2);
  96.     g1.addEdge(2, 3);
  97.     g1.addEdge(3, 0);
  98.     g1.addEdge(2, 4);
  99.     g1.addEdge(4, 2);
  100.     if (g1.isConnected())
  101.         cout<<"The Graph is Conneted"<<endl;
  102.     else
  103.         cout<<"The Graph is not Connected"<<endl;
  104.  
  105.     Graph g2(4);
  106.     g2.addEdge(0, 1);
  107.     g2.addEdge(1, 2);
  108.     g2.addEdge(2, 3);
  109.     if (g2.isConnected())
  110.         cout<<"The Graph is Connected"<<endl;
  111.     else
  112.         cout<<"The Graph is not Connected"<<endl;
  113.     return 0;
  114. }

advertisement
$ g++ directed_connected_bfs.cpp
$ a.out
The Graph is Not 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.

$ g++ directed_connected_dfs.cpp
$ a.out
The Graph is Connected
The Graph is Not 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