Count the number of connected components in an undirected graph

Problem Statement:

You are given an undirected graph. YOu need to find out the number of connected componenets in taht graph.

Example

Output: 3

Solution

We will use DFS to solve this problem.

We will initialize a boolean array “visited”.

Then for all the vertices we check if a vertex has been visited, if not visited we perform DFS on that vertex, then increment the count by 1.

We stop when all the vertices are visited and return the count.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   void helper(int v, bool visited[]); // helper function for check_if_connected
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   int count_connected_components(); // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   adj[w].push_back(v); 
}


void Graph::helper(int v, bool visited[])
{
      visited[v] = true;
      for(auto i = adj[v].begin(); i != adj[v].end(); i++)
      {
         int adjVertex = *i;

         if ( !visited[adjVertex]){
             helper(adjVertex, visited);
         }
      }
}

int Graph::count_connected_components()
{
    bool *visited = new bool[V];
    int count  = 0;

   for(int i = 0; i < V; i++)
   {
      visited[i] = false;
   }

    for (int v = 0; v < V; v++) 
    {
        if (visited[v] == false) {
            helper(v, visited);
            count ++;
        }
    }
   return count;
}


int main()
{

   Graph g(6);
   g.add_edge(1, 0);
   g.add_edge(2, 3);
   g.add_edge(3, 4);

   int count = g.count_connected_components();
   cout << "The number of connected components are "<<count<<endl;
   return 0;
}

Output:

The number of connected components are 4