CC-7 : Count components of the graph.

Description:

A component is a set of vertices connected to each other vis edges. A graph may consist of one component or multiple unconnected components. Given an input graph, count the number of components in the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphCountComponents gph=new GraphCountComponents(8); gph.addEdge(0, 1); gph.addEdge(1, 2); gph.addEdge(3, 4); gph.addEdge(4, 5); gph.addEdge(6, 7); retVal=gph.countComponents(); System.out.println(); System.out.println("Components: "); Iterator itr=retVal.iterator(); while (itr.hasNext()) { System.out.println(itr.next()); }	Each row below represents a component. Components: 0 1 2 3 4 5 6 7

Pseudocode:

Initialize an ArrayList named components to hold the vertices of components found while traversing the graph.

Iterate through vertices of the graph using a for loop with iIdx as loop variable with values from 0 to count of (vertices-1):

If visited[Idx] is not equal to 1:

Initialize String dfsTraversal to hold result of dfs traversal of graph from current vertex.

Call dfsTraversal() method with current vertex as input parameter to the method.

Add String dfsTraversal to ArrayList named components.

Code:

public class GraphCountComponents {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphCountComponents(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void dfsTraversal(int vertex) {
	  visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }	
 }
 
 public ArrayList<String> countComponents(){
	 ArrayList<String> components=new ArrayList<String>();
	 for (int idx=0; idx < vertices; idx++) {
		 if (visited[idx]==0) {
			 dfsTraversal=new String();
			 dfsTraversal(idx);
			 components.add(dfsTraversal);
		 }
	 }
	 return components;
 }
 }

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.Iterator;

public class GraphCountComponents {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphCountComponents(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void dfsTraversal(int vertex) {
	  visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }	
 }
 
 public ArrayList<String> countComponents(){
	 ArrayList<String> components=new ArrayList<String>();
	 for (int idx=0; idx < vertices; idx++) {
		 if (visited[idx]==0) {
			 dfsTraversal=new String();
			 dfsTraversal(idx);
			 components.add(dfsTraversal);
		 }
	 }
	 return components;
 }
 
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	ArrayList<String> retVal;
	try {
	GraphCountComponents gph=new GraphCountComponents(8);
	gph.addEdge(0, 1);
	gph.addEdge(1, 2);
	gph.addEdge(3, 4);
	gph.addEdge(4, 5);
	gph.addEdge(6, 7);
	retVal=gph.countComponents();
	System.out.println();
	System.out.println("Components: ");
	Iterator<String> itr=retVal.iterator();
	while (itr.hasNext()) {
		System.out.println(itr.next());
	}	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}