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.

#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




Related Contents to follow