We will be seeing the Recursive way for implementing Depth First Search (DFS).
In the Recursive code we don't have to create the stack and maintain it as java will do the job for us. And the stack will be hidden from us.
import java.util.Iterator; import java.util.LinkedList; public class DFSRecursion { static LinkedList<LinkedList<String>> adjacencyList; static LinkedList<String> vertices; static boolean visited[]; void insertVertex(String vertex) { vertices.add(vertex); } void constructAdjacencyList(String vtx, String adjcVertex) { int vtxIndex = vertices.indexOf(vtx); adjacencyList.add(new LinkedList<String>()); adjacencyList.get(vtxIndex).add(adjcVertex); } void depthFirstSearch(String source){ int sourceIndex = vertices.indexOf(source); visited[sourceIndex] = true; System.out.print(source+" "); for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) { String str = iter.next(); int i = vertices.indexOf(str); if (visited[i] == false) { visited[i] = true; depthFirstSearch(str); } } //System.out.print("\b\b\b\b"); } public static void main(String[] args) { int V = 6; DFSRecursion dfsRecursion = new DFSRecursion(); visited = new boolean[V]; adjacencyList = new LinkedList<LinkedList<String>>(); vertices = new LinkedList< >(); // Insert Vertices dfsRecursion.insertVertex("a"); dfsRecursion.insertVertex("b"); dfsRecursion.insertVertex("c"); dfsRecursion.insertVertex("d"); dfsRecursion.insertVertex("e"); dfsRecursion.insertVertex("f"); dfsRecursion.constructAdjacencyList("a", "c"); dfsRecursion.constructAdjacencyList("a", "d"); dfsRecursion.constructAdjacencyList("b", "d"); dfsRecursion.constructAdjacencyList("b" ,"e"); dfsRecursion.constructAdjacencyList("b" ,"c"); dfsRecursion.constructAdjacencyList("c", "a"); dfsRecursion.constructAdjacencyList("c", "b"); dfsRecursion.constructAdjacencyList("c", "e"); dfsRecursion.constructAdjacencyList("d", "a"); dfsRecursion.constructAdjacencyList("d" ,"b"); dfsRecursion.constructAdjacencyList("d", "e"); dfsRecursion.constructAdjacencyList("d", "f"); dfsRecursion.constructAdjacencyList("e", "b"); dfsRecursion.constructAdjacencyList("e", "c"); dfsRecursion.constructAdjacencyList("e", "d"); dfsRecursion.constructAdjacencyList("e", "f"); dfsRecursion.constructAdjacencyList("f", "d"); dfsRecursion.constructAdjacencyList("f", "e"); dfsRecursion.depthFirstSearch("a"); } }
We have implemented Depth First Search (DFS) on the below graph :
We can take various ways to navigate the graph using Depth First Search (DFS). Just remember our main intension is to visit all the vertices.
In this case we have covered the graph in the following path :
Let us see how ?
Below code explains the methods :
Almost the same we have discussed in DFS - Depth First Search - Iterative approach. You can skip it if you wane to.
Click Here - To understand the details of the methods 'void constructAdjacencyList(String vtx, String adjcVertex)' and 'void insertVertex(String vertex)'.
Let's list out, what all do we need to support Depth First Search Data Structure.
Now, let us see the above code.
We have a Linked List to store the Vertices.
We also have a doubly Linked List to store the Adjacency List.
Similarly, we have a stack defined inside the method 'depthFirstSearch(...)'.
And, there is a boolean array to store the Vertices that are visited.
So, the first thing we will do is, insert the Vertices to the 'LinkedList<String> vertices' Linked List.
void insertVertex(String vertex) { vertices.add(vertex); }
'void insertVertex(String vertex)' is quite simple.
There is just one statement in it.
It accepts 'String vertex' as a parameter and adds it to the Linked List, 'vertices'.
The next thing we will do is, create an Adjacency List to track the Adjacent Vertices.
Let us take the example of vertex 'a', to explain the creation of Adjacency List.
As we have seen, 'a' has two adjacent vertices(i.e. c and d). And we have used the constructAdjacencyList(...) method to construct the Adjacency Matrix.
void constructAdjacencyList(String vtx, String adjcVertex) { int vtxIndex = vertices.indexOf(vtx); adjacencyList.add(new LinkedList<String>()); adjacencyList.get(vtxIndex).add(adjcVertex); }
Although, the above method is explained in 'Adjacency List Code' tutorial. I will give a brief explanation in this tutorial.
When a method call is made,
The variable 'vtx' is assigned with value "a" and 'adjcVertex' is assigned with "b".
Now, the first line,
Calculates the index/position of Vertex 'a'. And as we can see the index 'a' is 0.
Now, in the next line,
We are initialising the first row of the 2D Linked List, 'adjacencyList'.
But with what?
We are initialising it with a Linked List 'new LinkedList<String>()',
So that the first row can hold the Adjacency List for vertex 'a'.
Similarly, the second row should hold the Adjacency List for vertex 'b' and so on.
And in this iteration, our target is to find out the first row(To create an Adjacency List for vertex 'a') and insert vertex 'b' to it.
And the below code does that.
We get the index of vertex 'a'
As we know 'vtx' is 'a'.
Then add 'adjcVertex'(That contains vertex 'c') to the 0th index of 'adjacencyList'.
And following it we form the Adjacency List.
Now, we come across the most important method 'void depthFirstSearch(String source)' that performs the Depth First Search (DFS).
void depthFirstSearch(String source){ int sourceIndex = vertices.indexOf(source); visited[sourceIndex] = true; System.out.print(source+" "); for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) { String str = iter.next(); int i = vertices.indexOf(str); if (visited[i] == false) { visited[i] = true; depthFirstSearch(str); } } }
We have called the 'void depthFirstSearch(String source)' from the main method passing 'a' as the parameter.
So, the first thing we will do is, take the index of 'a',
Now, if we see the List of vertices,
We can see that 'a' lies in index 0.
Next, we mark 'a' as visited,
in the 'visited[]' array,
Then we print the vertex 'a'.
Then comes the 'for(...)' loop, where we find the adjacent vertices of the top element(i.e. 'a').
for (Iterator<String> iter = adjacencyList.get(sourceIndex).iterator(); iter.hasNext(); ) { String str = iter.next(); int i = vertices.indexOf(str); if (visited[i] == false) { visited[i] = true; depthFirstSearch(str); } }
And the 'for' loop itself needs a little explanation.
Click Here - For the above for loop explanation.
'iter' variable of 'Iterator<String> iter', stores the Adjacency List of vertex 'a' in it.So, 'iter' has the elements 'c' and 'd' in it.
Now, 'str' contains the first adjacent vertex 'c'.
Next, we find the index of vertex 'c',
Now, if we see the List of vertices,
We can see that 'c' lies in index 2.
So, we check if 'c' is visited or not.
if (visited[i] == false) { visited[i] = true; depthFirstSearch(str); }
Now , if we check the visited array,
We found that 'visited[2] = false' and we get into the 'if' statement.
And marked visited[2] = true,
In the visited[] array ,
And then comes the fun part. Where the 'depthFirstSearch(...)' method calls itself.
So , internally what happens is, java maintains an internal stack, that is hidden from you.
Now , since the method started from 'a' , java puts 'a' to the stack. Then whenever it meets the statement,
It recognises a recursive call is made and pushes the content of variable 'str'(i.e. c) to the stack.
Similarly, we repeat the same process until all the vertices are visited. And java pushes all the values to the stack.
Now, since we have reached a place where all the adjacent vertices of vertex 'f' are visited.
So, it's time for java to backtrack. i.e. Start popping out all the elements from its internal queue.
So, it takes out 'f' out of the queue and checks if there are any adjacent vertices of 'e' that are not visited.
Continuing in the same way, all the elements are popped out of the Queue and the execution ends.