Number of Connected Components in an Undirected Graph

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++){
        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;
}

You can also try this code with Online C++ Compiler

Run Code

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);
    }
}

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.

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

Do upvote if you find the blogs helpful.

Happy Learning!