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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#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