Connected Components in Graph

Problem

Given an undirected graph with V vertices numbered from 0 to V-1 and E edges, represented as a 2D array edges[][], where each entry edges[i] = [u, v] denotes an edge between vertices u and v.

Your task is to return a list of all connected components. Each connected component should be represented as a list of its vertices, with all components returned in a collection where each component is listed separately.

Note: You can return the components in any order, driver code will print the components in sorted order. (Geeks Link)

Examples :

Input: V = 5, edges[][] = [[0, 1], [2, 1], [3, 4]]
Output: [[0, 1, 2], [3, 4]]
Explanation:

Input: V = 7, edges[][] = [[0, 1], [6, 0], [2, 4], [2, 3], [3, 4]]
Output: [[0, 1, 6], [2, 3, 4], [5]]
Explanation:

Constraints: 1 ≤ V ≤ 10⁵
1 ≤ edges.size() ≤ 10⁵
0 <= edges[i][0], edges[i][1] < V

Solution

• We visit each node and perform a complete traversal because the graph may not have all nodes connected. Therefore, we need to check each vertex to see if it has been traversed.(already visited)

        for(int vertex=0; vertex<V; vertex++) {
            if(visitedArray[vertex]!=1){
                traverse(vertex);
            }
        }

• Traversal is straightforward and is an extension of tree traversal, where we typically traverse left and right. Here, we traverse all the adjacent vertices of a particular node.

• In our case, each connected component is stored in a list, and we keep all these lists of components together.

• Note: We always prefer adjacency list over adjacency matrix because of the space complexity.

class Solution {
    private ArrayList<ArrayList<Integer>> createAdjacencyList(int V, int[][] edges) {
        ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<>();

        for(int i=0; i<V; i++){
            adjacencyList.add(new ArrayList<>());
        }

        for(int[] edge: edges){
            adjacencyList.get(edge[0]).add(edge[1]);
            adjacencyList.get(edge[1]).add(edge[0]);
        }

        return adjacencyList;
    }

    private void traverse(int vertex, int[] visitedArray, 
                            ArrayList<ArrayList<Integer>> adjacencyList, 
                            ArrayList<Integer> traversalList) {

        if(visitedArray[vertex] == 1) return;

        traversalList.add(vertex);
        visitedArray[vertex] = 1;

        for(Integer edgeVertex : adjacencyList.get(vertex)){
            traverse(edgeVertex, visitedArray, adjacencyList, traversalList);
        }

    }

    public ArrayList<ArrayList<Integer>> getComponents(int V, int[][] edges) {

        ArrayList<ArrayList<Integer>> adjacencyList = createAdjacencyList(V, edges);
        ArrayList<ArrayList<Integer>> connectedComponents = new ArrayList<>();
        int[] visitedArray = new int[V];

        for(int vertex=0; vertex<V; vertex++) {
            if(visitedArray[vertex]!=1){
                ArrayList<Integer> traversalList = new ArrayList<>();
                traverse(vertex, visitedArray, adjacencyList, traversalList);
                connectedComponents.add(traversalList);
            }
        }
        return connectedComponents;
    }
}