C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Check the Connectivity of Directed Graph Using BFS Program to Check the Connectivity of Directed Graph Using BFS This is a C++ Program to check the connectivity of directed graph using BFS. #include <iostream> #include <list> #include <queue> using namespace std; /* Class Declaration */ class Graph { private: int V; list<int> *adj; public: Graph(int V) { this->V = V; adj = new list<int> [V]; } void addEdge(int v, int w); void BFS(int s, bool visited[]); Graph getTranspose(); bool isConnected(); }; /* Add Edge to connect v and w */ void Graph::addEdge(int v, int w) { adj[v].push_back(w); //adj[w].push_back(v); } /* A recursive function to print BFS starting from s */ void Graph::BFS(int s, bool visited[]) { list<int> q; list<int>::iterator i; visited[s] = true; q.push_back(s); while (!q.empty()) { s = q.front(); q.pop_front(); for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; q.push_back(*i); } } } } /* Function that returns reverse (or transpose) of this graph */ Graph Graph::getTranspose() { Graph g(V); for (int v = 0; v < V; v++) { list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) { g.adj[*i].push_back(v); } } return g; } /* Check if Graph is Connected */ bool Graph::isConnected() { bool visited[V]; for (int i = 0; i < V; i++) visited[i] = false; BFS(0, visited); for (int i = 0; i < V; i++) if (visited[i] == false) return false; Graph gr = getTranspose(); for (int i = 0; i < V; i++) visited[i] = false; gr.BFS(0, visited); for (int i = 0; i < V; i++) if (visited[i] == false) return false; return true; } /* Main Contains Menu */ int main() { Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 3); g.addEdge(3, 3); if (g.isConnected()) cout << "The Graph 1 is Connected" << endl; else cout << "The Graph 1 is not Connected" << endl; Graph g1(5); g1.addEdge(0, 1); g1.addEdge(1, 2); g1.addEdge(2, 3); g1.addEdge(3, 0); g1.addEdge(2, 4); g1.addEdge(4, 2); if (g1.isConnected()) cout << "The Graph 2 is Connected" << endl; else cout << "The Graph 2 is not Connected" << endl; return 0; }