Connected components of graph

Connected components in graph

Given an undirected graph, find the number of connected components in it.

A connected component of an undirected graph is a maximal set of nodes such that each pair of nodes is connected by a path

Every vertex of the graph lies in a connected component that consists of all the vertices that can be reached from that vertex, together with all the edges that join those vertices. If an undirected graph is connected, there is only one connected component. Every graph has at least one connected component that is the graph itself.

For example in below graph, there are two connected components {1,2,3,4} and {5, 6}.

connected components in a graph

How to find the number of connected components in a graph?

We can find the number of Connected components in a graph by traversing the graph, either depth first traversal or breadth first traversal.

If we start from a node v and do a traversal of the graph, we will be able to reach all the nodes which are connected to this node through any path. These are the vertices which are part of this connected component.
Now, if there are some vertices still unvisited, then there must be another component of the graph. We start traversal again with the first unvisited vertex. We continue this until all the vertices are visited.

In the following implementation, we are using Depth First traversal of the graph to find the number of components.

Connected components of a graph: implementation

Implementation with adjacency list representation of graph

package com.company.Graphs;

import java.util.*;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyList {
    private Map<Integer, ArrayList<Integer>> G;
    boolean isDirected;

    public AdjacencyList(boolean isDirected){
        this.G = new HashMap<>();
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){

        if(this.G.containsKey(start)){
            this.G.get(start).add(dest);
        }else{
            this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
        }

        //In case graph is undirected
        if(!this.isDirected) {
            if (this.G.containsKey(dest)) {
                this.G.get(dest).add(start);
            } else {
                this.G.put(dest, new ArrayList<>(Arrays.asList(start)));
            }
        }
    }

    private void DFS(int node, boolean[] visited, 
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            this.G.get(node).forEach(v -> DFS(v, visited, traversal));
        }
    }

    public int connectedComponents(){

        boolean[] visited = new boolean[this.G.size()];
        int components = 0;

        for(int i=1; i<this.G.size(); i++) {
            ArrayList<Integer> traversal = new ArrayList<>();
            if(!visited[i]) {
                DFS(i, visited, traversal);
                System.out.println(traversal);
                components++;
            }
        }

        return components;
    }
}

Implementation using adjacency matrix representation of graph

package com.company.Graphs;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by sangar on 21.12.18.
 */
public class AdjacencyMatrix {
    private boolean [][] G;
    private boolean isDirected;

    public AdjacencyMatrix(int numNodes, boolean isDirected){
        this.G  = new boolean[numNodes+1][numNodes+1];
        this.isDirected = isDirected;
    }

    public void addEdge(int start, int dest){
        this.G[start][dest] = true;
        if(!isDirected){
            this.G[dest][start] = true;
        }
    }

    private void DFS(int node, boolean[] visited,
                     ArrayList<Integer> traversal){
        if(!visited[node]){
            traversal.add(node);
            visited[node] = true;

            for(int i=1; i< this.G[1].length; i++){
                if(this.G[node][i]){
                    DFS(i, visited, traversal);
                }
            }
        }
    }

    public int connectedComponents(){

        boolean[] visited = new boolean[this.G.length];
        int components = 0;

        for(int i=1; i<this.G.length; i++) {
            ArrayList<Integer> traversal = new ArrayList<>();
            if(!visited[i]) {
                DFS(i, visited, traversal);
                System.out.println(traversal);
                components++;
            }
        }
        return components;
    }
}

If an adjacency list representation is used, the for loop will run for i from 0
to V each time it is executed, so the runtime for the adjacency list representation is O(V2).

For an adjacency list representation of a graph, run time for the algorithm is O(V + E).

Please share if there is something wrong or missing. If you are preparing for an interview and want to get a free coaching session, please reach out to us at communications@algorithmsandme.com