# Check whether a given graph is connected or not

Write a c++ program to check whether a given graph is connected or not using DFS method. A graph is said to be connected when there is a path between every pair of nodes. In a connected graph, there are no unreachable nodes. A graph that is not connected is called disconnected graph.

*For example the below figure , the left side of graph is connected graph while the right side graph is disconnected graph.*

## *Check whether a given graph is connected or not*

To check whether a give graph is connected or not is simple. Here is simple steps to check.

*Run dfs algorithm starting from any vertex. ( To know more about dfs visit at http://wikistack.com/a-recursive-implementation-of-dfs/)**After finishing dfs , count the number of visited nodes.**If count is equal to number of vertices in graph, graph is connected else**Graph is disconnected.*

Here is simple implementation of above logic, please write comments if there is any problem with the code.

#include<iostream> #include <list> using namespace std; class G { int v; // No. of nodes // adjacency list list < int >*adj_list; // array for visited nodes bool *visited; public: G (int v); void add_edge (int u, int v); void reset_visited_array(); void dfs (int v); bool isConnected(); }; G::G (int v) { this->v = v; adj_list = new list < int >[v]; visited = new bool[v]; } void G::add_edge (int u, int v) { // graph is undirected // (u)--------------(v) adj_list[u].push_back (v); adj_list[v].push_back (u); } void G::reset_visited_array() { for(int i=0;i<v;i++) visited[i] = false; } // dfs function from vertex v. void G::dfs (int v) { if (!visited[v]) // make v visited visited[v] = true; //cout << v << " "; // find all adjacent nodes from vertex v list < int >::iterator i; for (i = adj_list[v].begin (); i != adj_list[v].end (); ++i) { // If an adjacent node is not visited if (!visited[*i]) { dfs (*i); } } } bool G::isConnected() { int count = 0; // count visited vertex for(int i=0; i < v; i++) { if( visited[i] ) // if node v is visited count++; } // check wheter the visited nodes count is equal // to the count of all nodes if( count == v ) return true; else return false; } int main () { // look the above graph there are six // nodes, the node number is starting from number 1 // so we will create 6 adjacency list G g (6); // make graph g.add_edge(0,1); g.add_edge(0,3); g.add_edge(1,2); g.add_edge(2,3); g.add_edge(3,5); g.add_edge(3,4); g.add_edge(4,5); // reset visited array // before starting dfs, make each visited false g.reset_visited_array(); // run dfs on graph G from vertex 1 g.dfs(1); if( g.isConnected() ) { cout<<"The graph is connected \n"; } else { cout<<"The graph is disconnected \n"; } G g1 (6); g1.add_edge(0,1); g1.add_edge(0,3); g1.add_edge(1,2); g1.add_edge(2,3); g1.add_edge(4,5); g1.reset_visited_array(); g1.dfs(1); if( g1.isConnected() ) { cout<<"The graph is connected \n"; } else { cout<<"The graph is disconnected \n"; } return 0; }

Ref:

https://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29

## Leave a Reply