Learn-dsa..in 30 days!



























CC-3 : Implement Depth First Search DFS Algorithm.

Description:

TDFS search is used for searching elements in graphs or trees. It starts from the root and searches to the deepest level vertex for a branch before back tracking and searching other vertices at upper levels of the current branch and then moves on to search other branches that emanate from the root. Given an input graph and an element to be searched, search the required element in the input graph using DFS search.

Test cases and expected outputs:

Input Parameters Expected outputs
Adjacency list:
vertex 0->1->2->3->4
vertex 1->0->2
vertex 2->0->1->3
vertex 3->0->2->4
vertex 4->0->3 		Dfs search path to : 4 is:
0 1 2 3 4
Adjacency list:
vertex 0->2->3->1
vertex 1->0
vertex 2->0->4
vertex 3->0
vertex 4->2 		Dfs search path to : 1 is:
0 2 4 3 1

Pseudocode:

The input vertices and edges of the graph should be converted into adjacency list format (refer chapter on graphs).
Initialize an integer array named visited to store information whether an particular vertex has been visited(processed).
Initialize a String variable named dfsTraversal to hold output of DFS traversal of the graph from root to the vertex to be searched.

Method dfsSearchRecursive(currVertex, toSearch):

Set visited[vertex] to 1, as the current vertex has been processed.
Add vertex to dfsTraversal String as it has been traversed now.
If currVertex==toSearch, return true from the method as we have found the vertex to be searched. We can check the value of dfsTraversal String as it contains the path of the required vertex from the root.
Extract vertices connected to vertex from the adjacencyList.
Initialize Boolean variable found to false.
Iterate through vertices connected to current vertex using iterator:
Set variable adjacentNode to point to current connected vertex in the iterator.
If visited[adjacentNode] is not 1, then:
Call dfsTraversal(adjacentNode) recursively.
If return value from above recursive call is true, return true from the method as we have found the vertex to be searched in the lower recursions.
If required vertex is not found in the above search, return false.

Code:

public class SearchDfsSearch {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public SearchDfsSearch(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 boolean dfsSearchRecursive(int currVertex,int toSearch) {
	 visited[currVertex]=1;
	 dfsTraversal+= currVertex + " ";
	 if (currVertex==toSearch) {
		 return true;
	 }
	 Iterator<Integer> itr=adjacencyLists.get(currVertex).iterator();
	 boolean found;
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 found=dfsSearchRecursive(adjacentNode, toSearch);
			 if (found==true) {
				 return true;
			 }
		 }
	 }
	return false;
 }
 }

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us