How to Find Connected Components in Graph

In this article, we are going to find connected components in a graph by building a program in C++ language. We are going to use different approaches to build the program for finding the connected components in the graph. We are also going to calculate the time complexity and the space complexity for the program.

Approach 1: Using Depth First Search (DFS)

An undirected graph's connected component search is simpler. In order to obtain all strongly connected components, the concept is to perform DFS starting from each unexplored vertices.

To put the concept into practice using DFS, we should follow the below mentioned steps:

• Set each vertex's initial state to unvisited.
• Follow these steps for each vertex v.
• Call the DFS and print the newline character to print each component in a new line if v has never been visited before.
• Print out v and mark it as visited.
• If a neighboring u of v is not visited, recursively call the DFS for that u.

Example 1:

// C++ program to print connected components in
// an undirected graph
#include
using namespace std;
// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
	int V; // No. of vertices


	// Pointer to an array containing adjacency lists
	list* adj;


	// A function used by DFS
	void DFSUtil(int v, bool visited[]);


public:
	Graph(int V); // Constructor
	~Graph();
	void addEdge(int v, int w);
	void connectedComponents();
};


// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
	// Mark all the vertices as not visited
	bool* visited = new bool[V];
	for (int v = 0; v < V; v++)
		visited[v] = false;


	for (int v = 0; v < V; v++) {
		if (visited[v] == false) {
			// print all reachable vertices
			// from v
			DFSUtil(v, visited);


			cout << "\n";
		}
	}
	delete[] visited;
}


void Graph::DFSUtil(int v, bool visited[])
{
	// Mark the current node as visited and print it
	visited[v] = true;
	cout << v << " ";


	// Recur for all the vertices
	// adjacent to this vertex
	list::iterator i;
	for (i = adj[v].begin(); i != adj[v].end(); ++i)
		if (!visited[*i])
			DFSUtil(*i, visited);
}


Graph::Graph(int V)
{
	this->V = V;
	adj = new list[V];
}


Graph::~Graph() { delete[] adj; }


// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
	adj[w].push_back(v);
}


// Driver code
int main()
{
	// Create a graph given in the above diagram
	Graph g(5); // 5 vertices numbered from 0 to 4
	g.addEdge(1, 0);
	g.addEdge(2, 1);
	g.addEdge(3, 4);


	cout << "Following are connected components \n";
	g.connectedComponents();


	return 0;
}

Output:

Following are connected components
0 1 2
3 4

Time complexity for the following program is - O(V+E).

Space complexity for the following program is - O(V).

Approach 2: Using Disjoint Set Union

In this approach, we first declare each node as a separate subset before visiting each one in order to tackle the problem using DSU (Disjoint Set Union). Join the under with any newly discovered unexplored nodes. In this way, each traversal will only visit one component.

To put the concept into practice, simply follow the below mentioned steps:

• Declare an array of size V called arr[], where V represents the total number of nodes.
• The value indicates who the parent of the ith vertex is for each index I of the array arr[].
• Every node should be created as its own parent, and as they are added together, their parents should be adjusted as necessary.
• From node 0 through node V, go around them:
• Start the DSU for each node that is its own parent.
• Print each node in the disjoint set as though it were a separate component.

Example 2:

#include <bits/stdc++.h>
using namespace std;


int merge(int* parent, int x)
{
    if (parent[x] == x)
        return x;
    return merge(parent, parent[x]);
}


int connectedcomponents(int n, vector >& edges)
{
    int parent[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    for (auto x : edges) {
        parent[merge(parent, x[0])] = merge(parent, x[1]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (parent[i] == i);
    }
    for (int i = 0; i < n; i++) {
        parent[i] = merge(parent, parent[i]);
    }
    map > m;
    for (int i = 0; i < n; i++) {
        m[parent[i]].push_back(i);
    }
    for (auto it = m.begin(); it != m.end(); it++) {
        list l = it->second;
        for (auto x : l) {
            cout << x << " ";
        }
        cout << endl;
    }
    return ans;
}


int main()
{
    int n = 5;
    vector e1 = { 0, 1 };
    vector e2 = { 2, 1 };
    vector e3 = { 3, 4 };
    vector > e;
    e.push_back(e1);
    e.push_back(e2);
    e.push_back(e3);


    cout << "Following are connected components:\n";
    int a = connectedcomponents(n, e);
    return 0;
}

Output:

Following are connected components
0 1 2
3 4

Time complexity for the program is - O(V)

Space complexity for the program is - O(V)