C++ Program to Check the Connectivity of Directed Graph Using BFS

«
»
This is a C++ Program to check the connectivity of directed graph using BFS.

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

Output:

$ g++ ConnectivityUsingBFSDiredctedGraph.cpp
$ a.out
 
The Graph 1 is not Connected
The Graph 2 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

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

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.