In this article, we will discuss about the Number of Connected Components in an Undirected Graph problem, along with a sample test case and approach to solve the problem.

Problem Statement

Given an undirected graph having V nodes labelled from 0 to V-1, the task is to find the number of connected components in the given undirected graph.

Sample Example

Input

Output

2

Explanation

For the above graph, there are 2 connected components: (0, 1 2) and (3, 4).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach

We are given an undirected graph having V nodes, and we are supposed to find the number of connected components in that graph. A connected component is a subgraph in which each pair of nodes is connected with each other through a path.

We can find the number of connected components in a graph using either of the graph traversal algorithms that are BFS & DFS. We maintain a count variable that keeps track of the number of components and a visited array to keep track of unvisited nodes.

In our approach, we will be using the DFS Algorithm. For every unvisited node that is encountered, we increment the count variable and call the DFS for that particular node. This approach works because whenever we call DFS for an unvisited node, it visits all of the nodes which are connected to that node, that is, by calling DFS for one node, we visit that particular component entirely.

Algorithm

Keep track of a count variable, and initialize it with 0. Also, maintain a visited array, initially marking every node as unvisited.

Perform the below-mentioned operations for every node v:

Check if node v is visited or not.

If unvisited, increment the count variable and call DFS for that particular node.

The implementation of the above algorithm in various programming languages is mentioned below:

C++ Code

#include <bits/stdc++.h>
using namespace std;
void DFS(int u, vector<bool> &visited, vector<int> adj[])
{
// mark the current node as visited
visited[u] = true;
// visit the neighbours
for(int i = 0; i<adj[u].size(); i++){
int v = adj[u][i];
if (visited[v]==false)
// recur for that node
DFS(v, visited, adj);
}
}
// function to calculate the no of components
int getConnectedComponents(vector<int> adj[], int V)
{
// stores the count of components
int count=0;
// visited array stores whether or not a node has been visited
vector<bool> visited(V, false);
// for every node
for (int u = 0; u < V; u++) {
// if not visited
if (visited[u] == false) {
// call DFS
DFS(u, visited, adj);
// increment no of components
count+=1;
}
}
return count;
}
// function to add an undirected edge between u & v
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Driver code
int main()
{
int V = 6;
vector<int> adj[V];
addEdge(adj, 1, 0);
addEdge(adj, 2, 3);
addEdge(adj, 5, 4);
addEdge(adj, 1, 3);
cout<<"The number of connected components are: "<<getConnectedComponents(adj, V);
return 0;
}

Java Code

import java.util.*;
class Solution
{
public static void DFS(int u, boolean visited[], ArrayList<ArrayList<Integer>> adj) {
//mark the current node as visited
visited[u] = true;
// visit the neighbours
for(Integer v: adj.get(u)) {
if(visited[v] == false) {
// recur for that node
DFS(v, visited, adj);
}
}
}
public static void getConnectedComponents(int V, ArrayList<ArrayList<Integer>> adj)
{
// stores the count of components
int count=0;
//visited array stores whether or not anode has been visited
boolean visited[] = new boolean[V];
// for every node
for(int i = 0;i<V;i++) {
// if not visited
if(visited[i]==false) {
// call DFS
DFS(i, visited, adj);
// increment the number of components
count+=1;
}
}
System.out.print("The number of connected components are " + count);
}
// function to add an undirected edge between u & v
public static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v){
adj.get(u).add(v);
adj.get(v).add(u);
}
public static void main(String args[]) {
ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
for (int i = 0; i < 6; i++) {
adj.add(new ArrayList < > ());
}
addEdge(adj, 1, 0);
addEdge(adj, 2, 3);
addEdge(adj, 5, 4);
addEdge(adj, 1, 3);
getConnectedComponents(6, adj);
}
}

Python Code

# to create an edge from u to v
def addEdge(adj, u, v):
adj[u].append(v)
adj[v].append(u)
# dfs search
def DFS(adj, visited, u):
# mark the current node as visited
visited[u]=1
# visit all the neighbours
for i in range(len(adj[u])):
# for every unvisited node call dfs
if visited[adj[u][i]] == 0:
DFS(adj, visited, adj[u][i])
# function to calculate the no of components
def getConnectedComponent (adj,V):
# count stores the no of components
count = 0
# visited is used to check whether or not a node is visited
visited = [0 for i in range(V)]
for u in range(V):
# for every unvisited node
if visited[u]==0:
# call dfs
DFS(adj, visited, u)
# increment the no of component
count+=1;
print(count)
# Driver Code
if __name__ == '__main__':
V = 6
adj = [[] for i in range(V)]
addEdge(adj, 1, 0);
addEdge(adj, 2, 3);
addEdge(adj, 5, 4);
addEdge(adj, 1, 3);
print("The number of connected components are: " , end=" ")
getConnectedComponent(adj, V)

Output:

The number of connected components are: 2

Complexities

Time Complexity

O(V+E), where V denotes the number of vertices and E denotes the number of edges

Space Complexity

O(V), where V denotes the number of vertices.

Frequently Asked Questions

What is the key difference between a graph and a tree?

The key difference between a graph and a tree is that a graph can have a cycle, but a tree cannot.

What is an undirected graph?

An undirected graph is a graph whose edges do not have a direction.

What is a connected component?

A connected component is a subgraph in which each pair of nodes is connected with each other through a path.

Conclusion

In this article, we have extensively discussed the Number of Connected Components in an Undirected Graph problem.

If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company.