CC-8 : Check if all vertices of the graph are reachable from a vertex in a directed graph.

Description:

In a directed graph, the edges are uni-directional from one vertex v1 to other vertice v2 (and not from v2 to v1 at the same time as it is in case of bi-directional/ undirectional graphs). Given an input uni-directional graph, check if all vertices are reachable from a particular vertex.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphDirectedCheckIfAllReachable gph= new GraphDirectedCheckIfAllReachable(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.addEdge(4, 1); gph.displayGraphAndCheckIfAllReachable();	Nodes traversable from 0 are: 0 1 2 3 4 All vertices are reachable from 0 Nodes traversable from 1 are: 1 2 3 4 Nodes traversable from 2 are: 2 3 4 1 Nodes traversable from 3 are: 3 4 1 2 Nodes traversable from 4 are: 4 1 2 3

Pseudocode:

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

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

Initialize int nodesReachable to hold count of vertices of graph reachable from current vertex.

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

Set visited[vIdx] to 0.

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

If values of nodesReachable is equal to count of input vertices, then all vertices of graph are reachable from current vertex.

Code:

public class GraphDirectedCheckIfAllReachable {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 private String dfsTraversal=new String();
 private int nodesReachable=0;
 
 public GraphDirectedCheckIfAllReachable(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);	 
 }
 
  
 public void dfsTraversal(int vertex) {
	 visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	nodesReachable++;
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }
	
} 
  
 public void displayGraphAndCheckIfAllReachable() {
	
	 for (int iIdx=0; iId  < vertices; iIdx++) {
		 System.out.println();
		 dfsTraversal="";
		 nodesReachable=0;
		 for (int vIdx=0; vIdx < vertices; vIdx++) {
			 visited[vIdx]=0;
		 }
		 dfsTraversal(iIdx);
		 System.out.print("Nodes traversable from "+iIdx+ " are "+ dfsTraversal);
		 if (nodesReachable==vertices) {			
			 System.out.print("  *All vertices are reachable from "+iIdx+" *");
		 }
	 }	
 }
 }

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 GraphDirectedCheckIfAllReachable {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 private String dfsTraversal=new String();
 private int nodesReachable=0;
 
 public GraphDirectedCheckIfAllReachable(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);	 
 }
 
  
 public void dfsTraversal(int vertex) {
	 visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	nodesReachable++;
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }
	
} 
  
 public void displayGraphAndCheckIfAllReachable() {
	
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 System.out.println();
		 dfsTraversal="";
		 nodesReachable=0;
		 for (int vIdx=0; vIdx < vertices; vIdx++) {
			 visited[vIdx]=0;
		 }
		 dfsTraversal(iIdx);
		 System.out.print("Nodes traversable from "+iIdx+ " are "+ dfsTraversal);
		 if (nodesReachable==vertices) {			
			 System.out.print("  *All vertices are reachable from "+iIdx+" *");
		 }
	 }	
 }

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	GraphDirectedCheckIfAllReachable gph=new GraphDirectedCheckIfAllReachable(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.addEdge(4, 1);
	gph.displayGraphAndCheckIfAllReachable();
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}