1.
Introduction
2.
Problem Statement
2.1.
Sample Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Approach
4.
Algorithm
5.
Code
5.1.
C++ Code
5.2.
Java Code
5.3.
Python Code
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
7.1.
What is the key difference between a graph and a tree?
7.2.
What is an undirected graph?
7.3.
What is a connected component?
8.
Conclusion
Last Updated: Mar 27, 2024
Medium

Number of Connected Components in an Undirected Graph

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

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

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.
• Else if visited, then continue.
• Return the count variable.

You can also read Detect cycle in an undirected graph here.

Code

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++){
if (visited[v]==false)
// recur for that node
}

}

// function to calculate the no of components
{
// 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
// increment no of components
count+=1;
}
}

return count;
}

// function to add an undirected edge between u & v
{
}

// Driver code
int main()
{
int V = 6;

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
if(visited[v] == false) {
// recur for that node
}
}
}
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
// 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 main(String args[]) {

ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();

for (int i = 0; i < 6; i++) {
}

}
}``````

Python Code

``````# to create an edge from u to v

# dfs search
# mark the current node as visited
visited[u]=1
# visit all the neighbours
# for every unvisited node call dfs

# function to calculate the no of components
# 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
# increment the no of component
count+=1;

print(count)

# Driver Code
if __name__ == '__main__':

V = 6
adj = [[] for i in range(V)]
print("The number of connected components are: " , end=" ")

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.

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.

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don't worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.

If you wish to enhance your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScript, 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.

Do upvote if you find the blogs helpful.

Happy Learning!

Live masterclass