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

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