C++ Program to Check the Connectivity of Directed Graph 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.

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.

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

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.