Connected components in undirected graph

Connected components in graph

Given an undirected graph, find out number of connected components in it. Connected components in undirected graph are subgraphs where each node is connected to other node in subgraph and not connected to any other vertex in graph. Every graph has at least one connected component that is graph itself. For example in below graph, there are two connected components {1,2,3,4} and {5, 6}.

Connected components in graph

Algorithms to find connected components

There are two methods to find connected components in undirected graph. First is to do depth first traversal of graph. If we start recursion afresh after terminating previous recursion for any starting node, then it means current node is not connected to any of the nodes traversed with recursion previously. Every time, this case happens, increment counter. To keep track of nodes in each connected component, color components of graph with different colors. To check if two nodes belong to same connected component, check if color is same.

Find connected components in graph implementation

#include<stdio.h>
#include<stdlib.h>

#define NUM_NODE 7
#define true 1
#define false 0
 
typedef struct node{
    int value;
    int wt;
    struct node *next;
}Node;
 
Node *graph[NUM_NODE + 1];
int visited[NUM_NODE + 1];

void dfs(Node * current){
    if(!current) return;
    visited[current->value] = true;
    Node *temp = current->next;
    while(temp){
        if(visited[temp->value] != true){
            dfs(graph[temp->value]);
        }
        temp = temp->next;
    }
}

int connected_component(Node * graph[]){
    int i, count =0;
    Node * current = NULL;
    for(i=0; i< NUM_NODE; i++){
        current  = graph[i];
        if(current && visited[current->value] == false){
            dfs(current);
            count++;
        }
    }
    return count;
}

Node * createNode(int j){
 
    Node * newNode = (Node *)malloc(sizeof(Node));
    if(newNode){
        newNode->value = j;
        newNode->next = NULL;
    }
    else{
        printf("\n Node cannot be allocated");
    }
    return newNode;
}
 
void addEdge(int i, int j){
 
    Node * currentNode = graph[i];
    if(!currentNode){
        graph[i] = createNode(j);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(j);
    }
}

//Driver program
int main(){

	for(int i=1; i<=NUM_NODE; i++){
		graph[i] = createNode(i);
	}
	
	addEdge(1,2);
	addEdge(1,5);
	addEdge(2,3);
	addEdge(2,4);
	addEdge(4,1);
	addEdge(3,4);
	addEdge(4,6);
	addEdge(5,4);
	addEdge(5,6);
	
	for(int i=1; i<=NUM_NODE; i++){
        visited[i] = false;
    }

    int count = connected_component(graph);
    printf("\n Number of connected component : %d", count);
    
    return 0;
}

Complexity of above code will be complexity of depth first search O(V+E) with extra space of O(N) to store color of connected components.

Connected components : Union and Find method

Second method to undirected graph is to use Union and Find method as discussed in previous post :Graphs : Detecting cycle in undirected graph

Go through all nodes of graph and create disjoint sets. After that, check how many disjoint sets are formed, that gives us number of connected components. To check if two nodes are connected, see if both nodes are in same disjoint set.

Find connected components in graph using Union and Find method Implementation

#include<stdio.h>
#include<stdlib.h>

#define NUM_NODE 6
#define true 1
#define false 0
 
typedef struct node{
    int value;
    struct node *next;
}Node;
 
Node *graph[NUM_NODE + 1];

int find(int rep[], int value){
	if(rep[value] == -1 || rep[value] == value)
		return value;
	else find(rep, rep[value]);
}

void unionSet(int rep[], int x, int y){
	int xroot = find(rep, x);
	int yroot = find(rep, y);
	
	rep[xroot] = yroot;
}

void makeSet(int rep[]){
	for(int i=1; i<= NUM_NODE; i++){
		rep[i] = -1;
    }
}

int connectedComponent(Node * graph[]){

    int rep[NUM_NODE + 1] ;
    int count = 1;

    makeSet(rep);
    for(int i=1; i<= NUM_NODE; i++){
        Node * u =  graph[i];
        if(u){
            Node *v = u->next;
            
            while(v){
                int x = find(rep, u->value);
                int y = find(rep, v->value);
                
                unionSet(rep, x,y);
                v = v->next;
              
            }
        }
    }
    
    for(int i=1; i<= NUM_NODE; i++){
       	if(rep[i] == -1 ){
             count++;
        }
    }
    return count;
}

Node * createNode(int j){
 
    Node * newNode = (Node *)malloc(sizeof(Node));
    if(newNode){
        newNode->value = j;
        newNode->next = NULL;
    }
    else{
        printf("\n Node cannot be allocated");
    }
    return newNode;
}
 
void addEdge(int i, int j){
 
    Node * currentNode = graph[i];
    if(!currentNode){
        graph[i] = createNode(j);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(j);
    }
}
//Driver program
int main(){

	for(int i=1; i<=NUM_NODE; i++){
		graph[i] = createNode(i);
	}
	
	addEdge(1,2);
	addEdge(1,5);
	addEdge(2,3);
	addEdge(2,4);
	addEdge(4,1);
	addEdge(3,4);
	addEdge(5,4);
	
   	int count = connectedComponent(graph);
	printf("\n Number of connected components in graph : %d", count);
	
	return 0;
}

Complexity of Union and find method is again O(V+E) with extra space to store representative element of each disjoint set.
Please share if there is something missing or wrong. If you are interested in contributing to website or have an interview experience to share, please contact us. You can earn too!