We will be seeing the Iterative way for implementing Depth First Search (DFS). Although there are various ways to write this Iterative code.
However, we will write the code little differently. So that you can corelate it with the Depth First Search (DFS) explanation.
In the Iterative code we will create the stack and maintain it ourselves.
<html> <body> <script> function insertVertex(vertex) { vertices.push(vertex) } function constructAdjacencyList(vtx, adjcVertex) { var vtxIndex = vertices.indexOf(vtx) adjacencyList.push([]) adjacencyList[vtxIndex].push(adjcVertex) } function depthFirstSearch(source) { var sourceIndex = vertices.indexOf(source) visited[sourceIndex] = true var stack = [] stack.push(source) document.write(source, " --> ") while (stack.length !== 0) { source = stack[stack.length-1] // Peek operation sourceIndex = vertices.indexOf(source) var str = "" for (iter of adjacencyList[sourceIndex]) { str = iter i = vertices.indexOf(str) if (visited[i] == false) { stack.push(str) visited[i] = true document.write(str, " --> ") break } } if (stack[stack.length-1] != str) { stack.pop() } } document.write("</br>") } const V = 6 var visited = new Array(V).fill(false) var adjacencyList = [[]] var vertices = [] // Insert Vertices insertVertex("a") insertVertex("b") insertVertex("c") insertVertex("d") insertVertex("e") insertVertex("f") constructAdjacencyList("a", "c") constructAdjacencyList("a", "d") constructAdjacencyList("b", "d") constructAdjacencyList("b" ,"e") constructAdjacencyList("b" ,"c") constructAdjacencyList("c", "a") constructAdjacencyList("c", "b") constructAdjacencyList("c", "e") constructAdjacencyList("d", "a") constructAdjacencyList("d" ,"b") constructAdjacencyList("d", "e") constructAdjacencyList("d", "f") constructAdjacencyList("e", "b") constructAdjacencyList("e", "c") constructAdjacencyList("e", "d") constructAdjacencyList("e", "f") constructAdjacencyList("f", "d") constructAdjacencyList("f", "e") depthFirstSearch("a") </script> </body> </html>
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 :
a --> c --> b --> d --> e --> f -->
Let us see how?
Below code explains the methods :
Almost the same we have discussed in BFS. You can skip it if you wane to.
Click Here - To understand the details of the methods 'function constructAdjacencyList(vtx, adjcVertex)' and 'function insertVertex(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.
vertices
We also have a doubly Linked List to store the Adjacency List.
adjacencyList
Similarly, we have a stack defined inside the method depthFirstSearch(...).
stack
And, there is a boolean array to store the Vertices that are visited.
visited
So, the first thing we will do is, insert the Vertices to the vertices Linked List.
var vertices = [] // Insert Vertices insertVertex("a") insertVertex("b") insertVertex("c") insertVertex("d") insertVertex("e") insertVertex("f")
function insertVertex(vertex) { vertices.push(vertex) }
function insertVertex(vertex) is quite simple.
There is just one statement in it.
vertices.push(vertex)
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.
constructAdjacencyList("a", "c") constructAdjacencyList("a", "d")
function constructAdjacencyList(vtx, adjcVertex) { var vtxIndex = vertices.indexOf(vtx) adjacencyList.push([]) adjacencyList[vtxIndex].push(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,
vtxIndex = vertices.indexOf(vtx)
Calculates the index/position of Vertex a. And as we can see the index a is 0.
Now, in the next line,
adjacencyList.push([])
We are initialising the first row of the 2D Linked List, adjacencyList.
But with what?
We are initialising it with an Array [],
adjacencyList.push([])
So that the first row can hold the Adjacency List for vertex a.
a --- c ---> d
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.
adjacencyList[vtxIndex].push(adjcVertex)
We get the index of vertex a
vtxIndex = vertices.indexOf(vtx)
As we know vtx is a.
Then add adjcVertex(That contains vertex c) to the 0th index of adjacencyList.
adjacencyList[0].push("c")
And following it we form the Adjacency List.
Now, we come across the most important method function depthFirstSearch(source) that performs the Depth First Search (DFS).
function depthFirstSearch(source) { var sourceIndex = vertices.indexOf(source) visited[sourceIndex] = true var stack = [] stack.push(source) document.write(source, " --> ") while (stack.length !== 0) { source = stack[stack.length-1] // Peek operation sourceIndex = vertices.indexOf(source) var str = "" for (iter of adjacencyList[sourceIndex]) { str = iter i = vertices.indexOf(str) if (visited[i] == false) { stack.push(str) visited[i] = true document.write(str, " --> ") break } } if (stack[stack.length-1] != str) { stack.pop() } } document.write("</br>") }
We have called the function depthFirstSearch(source) from the main method passing a as the parameter.
depthFirstSearch("a")
So, the first thing we will do is, take the index of a,
sourceIndex = vertices.indexOf(source)
Now, if we see the List of vertices,
We can see that a lies in index 0.
Next, we mark a as visited,
visited[sourceIndex] = true
in the visited[] array,
visited[0] = true;
Then, we create the stack,
stack = []
And the immediate next thing we do is, push a to the stack.
stack.push(source)
Then we print the vertex a.
document.write(str, " --> ")
Next, we enter the while() loop that continues until the stack is not empty.
while (stack.length !== 0) { source = stack[stack.length-1] // Peek operation sourceIndex = vertices.indexOf(source) var str = "" for (iter of adjacencyList[sourceIndex]) { str = iter i = vertices.indexOf(str) if (visited[i] == false) { stack.push(str) visited[i] = true document.write(str, " --> ") break } } if (stack[stack.length-1] != str) { stack.pop() } }
In the while() loop, we take the top element(i.e. a) in the source variable.
source = stack[stack.length-1] // Peek operation
The we take the index of the top element(0 is the index of a).
sourceIndex = vertices.indexOf(source)
Then comes the for(...) loop, where we find the find the adjacent vertices of the top element(i.e. a).
for (iter of adjacencyList[sourceIndex]) { str = iter i = vertices.indexOf(str) if (visited[i] == false) { stack.push(str) visited[i] = true document.write(str, " --> ") break } }
The first statement of the for loop (i.e. The initialisation section of the loop),
iter
is where we get the Adjacent Vertices of vertex c in the iter.
Thinking How ?
Well ! The adjacencyList is a 2D Linked List that stores the adjacent vertices. And the trick is played in,
adjacencyList[sourceIndex]
As we have seen, the sourceIndex is 0 (Because the index of vertex a is 0).
And the iter variable of iter gets the adjacency list of vertex a in it.
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.
str = iter
Next, we find the index of vertex c,
i = vertices.indexOf(str)
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) { stack.push(str) visited[i] = true document.write(str, " --> ") break }
Now, if we check the visited array,
We found that visited[2] = false and we get into the if statement.
So, we push c to the Queue.
And marked visited[2] = true,
visited[i] = true;
In the visited[] array,
then we break out of the for loop
break
After getting out of the for loop, we check if the value inside the str variable and the top element are equal or not.
if (stack[stack.length-1] != str) { stack.pop() }
In this case str has c inside it and the top element of the stack is also c.
So, we don't pop c out of the stack and continue with the while loop.
Similarly, we repeat the same process until all the vertices are visited.
Now, let's visit the while() loop again.
The top element is f now,
source = stack[stack.length-1] // Peek operation
So, the value of source variable is f and
sourceIndex = vertices.indexOf(source)
the value of sourceIndex variable would be 5.
Now, the adjacent vertices of f are d and e.
for (iter of adjacencyList[sourceIndex])
So, the variable str would contain d(Since, the adjacent vertices of f are d and e) in the first iteration and would be e in the second iteration.
str = iter i = vertices.indexOf(str)
And both e and d are visited. So, the lines under the if statement are never visited.
if (visited[i] == false) { stack.push(str) visited[i] = true document.write(str, " --> ") break }
So, the for loop completes. And the value of the variable str would be e.
So, after getting out of the for loop, we check if the value inside the str variable and the top element are equal or not.
if (stack[stack.length-1] != str) { stack.pop() }
In this case the top element is f and the value in str is e.
And the if (stack[stack.length-1] != str) condition matches and f is popped out of the queue.
stack.pop()
Continuing in the same way, all the elements are popped out of the Queue and the execution ends.