Given an undirected graph, the task is to print all the connected components line by line.
Examples:
Input: Consider the following graph
Example of an undirected graph
Output:
0 1 2
3 4
Explanation: There are 2 different connected components.
They are {0, 1, 2} and {3, 4}.
We have discussed algorithms for finding strongly connected components in directed graphs in following posts.
Kosaraju’s algorithm for strongly connected components.
Tarjan’s Algorithm to find Strongly Connected Components
Connected Components for undirected graph using DFS:
Finding connected components for an undirected graph is an easier task. The idea is to
Do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components.
Follow the steps mentioned below to implement the idea using DFS:
- Initialize all vertices as not visited.
- Do the following for every vertex v:
- If v is not visited before, call the DFS. and print the newline character to print each component in a new line
- Mark v as visited and print v.
- For every adjacent u of v, If u is not visited, then recursively call the DFS.
- If v is not visited before, call the DFS. and print the newline character to print each component in a new line
Below is the implementation of above algorithm.
C++
// C++ program to print connected components in// an undirected graph#include <bits/stdc++.h>using namespace std;// Graph class represents a undirected graph// using adjacency list representationclass Graph { int V; // No. of vertices // Pointer to an array containing adjacency lists list<int>* 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 graphvoid 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<int>::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<int>[V];}Graph::~Graph() { delete[] adj; }// method to add an undirected edgevoid Graph::addEdge(int v, int w){ adj[v].push_back(w); adj[w].push_back(v);}// Driver codeint 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;} |
Java
// Java program to print connected components in// an undirected graphimport java.util.ArrayList;class Graph { // A user define class to represent a graph. // A graph is an array of adjacency lists. // Size of array will be V (number of vertices // in graph) int V; ArrayList<ArrayList<Integer> > adjListArray; // constructor Graph(int V) { this.V = V; // define the size of array as // number of vertices adjListArray = new ArrayList<>(); // Create a new list for each vertex // such that adjacent nodes can be stored for (int i = 0; i < V; i++) { adjListArray.add(i, new ArrayList<>()); } } // Adds an edge to an undirected graph void addEdge(int src, int dest) { // Add an edge from src to dest. adjListArray.get(src).add(dest); // Since graph is undirected, add an edge from dest // to src also adjListArray.get(dest).add(src); } void DFSUtil(int v, boolean[] visited) { // Mark the current node as visited and print it visited[v] = true; System.out.print(v + " "); // Recur for all the vertices // adjacent to this vertex for (int x : adjListArray.get(v)) { if (!visited[x]) DFSUtil(x, visited); } } void connectedComponents() { // Mark all the vertices as not visited boolean[] visited = new boolean[V]; for (int v = 0; v < V; ++v) { if (!visited[v]) { // print all reachable vertices // from v DFSUtil(v, visited); System.out.println(); } } } // Driver code public static void main(String[] args) { // Create a graph given in the above diagram Graph g = new Graph(5); g.addEdge(1, 0); g.addEdge(2, 1); g.addEdge(3, 4); System.out.println( "Following are connected components"); g.connectedComponents(); }} |
Python3
# Python program to print connected# components in an undirected graphclass Graph: # init function to declare class variables def __init__(self, V): self.V = V self.adj = [[] for i in range(V)] def DFSUtil(self, temp, v, visited): # Mark the current vertex as visited visited[v] = True # Store the vertex to list temp.append(v) # Repeat for all vertices adjacent # to this vertex v for i in self.adj[v]: if visited[i] == False: # Update the list temp = self.DFSUtil(temp, i, visited) return temp # method to add an undirected edge def addEdge(self, v, w): self.adj[v].append(w) self.adj[w].append(v) # Method to retrieve connected components # in an undirected graph def connectedComponents(self): visited = [] cc = [] for i in range(self.V): visited.append(False) for v in range(self.V): if visited[v] == False: temp = [] cc.append(self.DFSUtil(temp, v, visited)) return cc# Driver Codeif __name__ == "__main__": # Create a graph given in the above diagram # 5 vertices numbered from 0 to 4 g = Graph(5) g.addEdge(1, 0) g.addEdge(2, 1) g.addEdge(3, 4) cc = g.connectedComponents() print("Following are connected components") print(cc)# This code is contributed by Abhishek Valsan |
C#
using System;using System.Collections.Generic;class Graph{ // A user defined class to represent a graph. // A graph is an array of adjacency lists. // Size of array will be V (number of vertices // in graph) int V; List<List<int>> adjListArray; // constructor public Graph(int V) { this.V = V; // define the size of array as // number of vertices adjListArray = new List<List<int>>(); // Create a new list for each vertex // such that adjacent nodes can be stored for (int i = 0; i < V; i++) { adjListArray.Add(new List<int>()); } } // Adds an edge to an undirected graph public void addEdge(int src, int dest) { // Add an edge from src to dest. adjListArray[src].Add(dest); // Since graph is undirected, add an edge from dest // to src also adjListArray[dest].Add(src); } void DFSUtil(int v, bool[] visited) { // Mark the current node as visited and print it visited[v] = true; Console.Write(v + " "); // Recur for all the vertices // adjacent to this vertex foreach (int x in adjListArray[v]) { if (!visited[x]) DFSUtil(x, visited); } } public void connectedComponents() { // Mark all the vertices as not visited bool[] visited = new bool[V]; for (int v = 0; v < V; ++v) { if (!visited[v]) { // print all reachable vertices // from v DFSUtil(v, visited); Console.WriteLine(); } } } // Driver code public static void Main(string[] args) { // Create a graph given in the above diagram Graph g = new Graph(5); g.addEdge(1, 0); g.addEdge(2, 1); g.addEdge(3, 4); Console.WriteLine("Following are connected components:"); g.connectedComponents(); }}// This code is contributed by lokeshpotta20. |
Javascript
<script>// Javascript program to print connected components in// an undirected graph// A user define class to represent a graph. // A graph is an array of adjacency lists. // Size of array will be V (number of vertices // in graph)let V;let adjListArray=[];// constructorfunction Graph(v){ V = v // define the size of array as // number of vertices // Create a new list for each vertex // such that adjacent nodes can be stored for (let i = 0; i < V; i++) { adjListArray.push([]); }}// Adds an edge to an undirected graphfunction addEdge(src,dest){ // Add an edge from src to dest. adjListArray[src].push(dest); // Since graph is undirected, add an edge from dest // to src also adjListArray[dest].push(src);}function DFSUtil(v,visited){ // Mark the current node as visited and print it visited[v] = true; document.write(v + " "); // Recur for all the vertices // adjacent to this vertex for (let x = 0; x < adjListArray[v].length; x++) { if (!visited[adjListArray[v][x]]) DFSUtil(adjListArray[v][x], visited); }}function connectedComponents(){ // Mark all the vertices as not visited let visited = new Array(V); for(let i = 0; i < V; i++) { visited[i] = false; } for (let v = 0; v < V; ++v) { if (!visited[v]) { // print all reachable vertices // from v DFSUtil(v, visited); document.write("<br>"); } }}// Driver codeGraph(5);addEdge(1, 0);addEdge(2, 1);addEdge(3, 4);document.write("Following are connected components<br>");connectedComponents();// This code is contributed by rag2127</script> |
Output
Following are connected components 0 1 2 3 4
Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V)
Connected Component for undirected graph using Disjoint Set Union:
The idea to solve the problem using DSU (Disjoint Set Union) is
Initially declare all the nodes as individual subsets and then visit them. When a new unvisited node is encountered, unite it with the under. In this manner, a single component will be visited in each traversal.
Follow the below steps to implement the idea:
- Declare an array arr[] of size V where V is the total number of nodes.
- For every index i of array arr[], the value denotes who the parent of ith vertex is.
- Initialise every node as the parent of itself and then while adding them together, change their parents accordingly.
- Traverse the nodes from 0 to V:
- For each node that is the parent of itself start the DSU.
- Print the nodes of that disjoint set as they belong to one component.
Below is the implementation of the above approach.
C++
#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<vector<int> >& 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<int, list<int> > m; for (int i = 0; i < n; i++) { m[parent[i]].push_back(i); } for (auto it = m.begin(); it != m.end(); it++) { list<int> l = it->second; for (auto x : l) { cout << x << " "; } cout << endl; } return ans;}int main(){ int n = 5; vector<int> e1 = { 0, 1 }; vector<int> e2 = { 2, 1 }; vector<int> e3 = { 3, 4 }; vector<vector<int> > 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;} |
Java
import java.util.*;class ConnectedComponents { public static int merge(int[] parent, int x) { if (parent[x] == x) return x; return merge(parent, parent[x]); } public static int connectedComponents(int n, List<List<Integer>> edges) { int[] parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } for (List<Integer> x : edges) { parent[merge(parent, x.get(0))] = merge(parent, x.get(1)); } int ans = 0; for (int i = 0; i < n; i++) { if (parent[i] == i) ans++; } for (int i = 0; i < n; i++) { parent[i] = merge(parent, parent[i]); } Map<Integer, List<Integer>> m = new HashMap<>(); for (int i = 0; i < n; i++) { m.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i); } for (Map.Entry<Integer, List<Integer>> it : m.entrySet()) { List<Integer> l = it.getValue(); for (int x : l) { System.out.print(x + " "); } System.out.println(); } return ans; } public static void main(String[] args) { int n = 5; List<List<Integer>> edges = new ArrayList<>(); edges.add(Arrays.asList(0, 1)); edges.add(Arrays.asList(2, 1)); edges.add(Arrays.asList(3, 4)); System.out.println("Following are connected components:"); int ans = connectedComponents(n, edges); }} |
C#
using System;using System.Collections.Generic;class ConnectedComponents {public static int Merge(int[] parent, int x) {if (parent[x] == x)return x;return Merge(parent, parent[x]);}public static int CountConnectedComponents(int n, List<List<int>> edges) { int[] parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } foreach (List<int> x in edges) { parent[Merge(parent, x[0])] = Merge(parent, x[1]); } int ans = 0; for (int i = 0; i < n; i++) { if (parent[i] == i) ans++; } for (int i = 0; i < n; i++) { parent[i] = Merge(parent, parent[i]); } Dictionary<int, List<int>> m = new Dictionary<int, List<int>>(); for (int i = 0; i < n; i++) { if (!m.ContainsKey(parent[i])) { m[parent[i]] = new List<int>(); } m[parent[i]].Add(i); } foreach (KeyValuePair<int, List<int>> it in m) { List<int> l = it.Value; foreach (int x in l) { Console.Write(x + " "); } Console.WriteLine(); } return ans;}public static void Main() { int n = 5; List<List<int>> edges = new List<List<int>>(); edges.Add(new List<int> { 0, 1 }); edges.Add(new List<int> { 2, 1 }); edges.Add(new List<int> { 3, 4 }); Console.WriteLine("Following are connected components:"); int ans = CountConnectedComponents(n, edges);}} |
Python3
# Python equivalent of above Java code# importing utilitiesimport collections# class to find connected componentsclass ConnectedComponents: # function to merge two components def merge(self, parent, x): if parent[x] == x: return x return self.merge(parent, parent[x]) # function to find connected components def connectedComponents(self, n, edges): # list to store parents of each node parent = [i for i in range(n)] # loop to set parent of each node for x in edges: parent[self.merge(parent, x[0])] = self.merge(parent, x[1]) # count to store number of connected components ans = 0 # loop to count number of connected components for i in range(n): if parent[i] == i: ans += 1 # loop to merge all components for i in range(n): parent[i] = self.merge(parent, parent[i]) # map to store parent and its connected components m = collections.defaultdict(list) for i in range(n): m[parent[i]].append(i) # loop to print connected components for it in m.items(): l = it[1] print(" ".join([str(x) for x in l])) return ans# driver codeif __name__ == "__main__": n = 5 edges = [[0, 1], [2, 1], [3, 4]] # print connected components print("Following are connected components:") ans = ConnectedComponents().connectedComponents(n, edges) |
Javascript
// JavaScript program to find connected components in a graph// Function to find the parent of a node using path compressionfunction merge(parent, x) { if (parent[x] === x) { return x; } return merge(parent, parent[x]);}// Function to find the number of connected components in the graphfunction connectedcomponents(n, edges) { // Initialize parent array for each node let parent = []; for (let i = 0; i < n; i++) { parent[i] = i; } // Union operation for all edges for (let x of edges) { parent[merge(parent, x[0])] = merge(parent, x[1]); } // Count the number of nodes with self as parent, which are the roots of connected components let ans = 0; for (let i = 0; i < n; i++) { ans += parent[i] === i; } // Find the parent of each node again, and group nodes with the same parent for (let i = 0; i < n; i++) { parent[i] = merge(parent, parent[i]); } let m = new Map(); for (let i = 0; i < n; i++) { if (!m.has(parent[i])) { m.set(parent[i], []); } m.get(parent[i]).push(i); } // Print the nodes in each connected component console.log("Following are connected components:"); for (let [key, value] of m) { console.log(value.join(" ")); } // Return the number of connected components return ans;}// Sample inputlet n = 5;let e1 = [0, 1];let e2 = [2, 1];let e3 = [3, 4];let e = [e1, e2, e3];// Find connected components and print themlet a = connectedcomponents(n, e); |
Output
Following are connected components: 0 1 2 3 4
Time Complexity: O(V)
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
