CC-4 : Implement Bi-directional/ Undirectional graph Depth First (DFS) traversal.

Description:

Create and test a unidirectional Graph DFS Traversal program.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphDfs gph=new GraphDfs(5); gph=new GraphDfs(5); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 1); gph.addEdge(2, 4); gph.displayGraph(); gph.dfsTraversal(0); System.out.println(); System.out.println("Dfs Traversal: "+ gph.dfsTraversal);	vertex 0->2->3->1 vertex 1->0 vertex 2->0->4 vertex 3->0 vertex 4->2 Dfs Traversal: 0 2 4 3 1

Pseudocode:

Initialize an int variable named visited to store information whether a particular vertice in the graph has been visited.

Initialize a String variable named dfsTraversal to hold output of DFS traversal of the graph.

Method dfsTraversal(int vertex):

Set visited[vertex] to 1.

Add vertex to dfsTraversal String as it has been traversed now.

Extract vertices connected to vertex from the adjacencyList.

Iterate through vertices connected to current vertex using iterator:

Set variable adjacentNode to point to current connected vertice in the iterator.

If visited[adjacentNode] is not 1, then:

Call dfsTraversal(adjacentNode) recursively.

Code:

public class GraphDfs {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphDfs(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);
		 }
	 }
	
 } 
 }

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

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphDfs(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 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:
	 **********************/
	String retVal;
	try {
	GraphDfs gph=new GraphDfs(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.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	
	gph=new GraphDfs(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(2, 4);
	gph.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	
	gph=new GraphDfs(5);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 1);
	gph.addEdge(2, 4);
	gph.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}