Welcome back.
Let's now go ahead and code the function which will traverse this graph over here with depth.
First search.
And we will implement this function in an iterative manner.
So let's call this function graph DFS iterative.
All right.
And this function is going to take in the graph as a parameter.
And we also need to mention the starting vertex.
So these are the two parameters for this function.
Now inside this function we will have the output array.
So initially this is going to be an empty array.
And then we will just traverse the graph and push values to it.
And finally we will return this output array.
So this is going to be our function.
Now we also need a visited object.
So let's say const visited.
And initially it's going to be empty.
Now when we call this function initially we are going to pass the start vertex.
So we can at this point push this start to our stack.
Right.
We have discussed that to do DFS iteratively we will be using a stack.
So again let's create that stack over here.
Let's initialize it const stack.
And when we initialize it itself we can push start to it.
And we can mark start as visited.
So we can say visited at start is equal to true.
All right.
Now we are going to have our while loop.
And again let's have a variable current so that we don't again and again initialize it inside the while
loop.
Now this while loop will run so long as something is there in the stack.
So while stack dot length greater than zero, the while loop will keep iterating or looping right?
And then inside this we are going to identify the current value as the uh last in right.
So the the last in structure stack is a linear structure.
So what what came in last will be taken out first.
So we are just going to pop the last element from the stack.
So we can say stack.pop.
So we remove the last element right last in first out.
And we take that element and we are going to push it to our output array.
So output dot push and current right.
So we are going to push current to our output array.
So this will ensure that we push to the output array children nodes before neighbor nodes.
So that is why we are popping right.
If you remember the BFS implementation we had a queue and we were taking from the beginning of the queue
so that we have neighbors before children.
But over here we are doing DFS and we want children before neighbors.
That is why we are taking from the end.
So that's why we have used a stack and hence we are popping over here.
All right.
So we pop the last element out, take the last element out and we push it to the output array.
And then we are going to identify its neighbors.
So we can say const.
Neighbors.
Is equal to.
Graph.
At current.
All right.
So for example if current is a then the neighbors would be this array over here which is b and f.
All right.
So we get an array over here.
Now we are going to loop through this array using a for loop.
So let's say for let I is equal to zero I less than neighbors dot length I plus plus.
So we loop through the array neighbors.
And we will take each neighbor and check if it's there in the visited hash table or not.
So let's say if not visited at neighbors at I right.
So neighbors at I will be one particular neighbor.
So we are going to check whether that is there in our visited object or not or hash table.
Right.
So if it is not there, that is if this is undefined, that means there is no entry where the key is
that particular neighbor.
In that case we are going to push it to our stack.
So stack dot push neighbors at I.
All right.
And then we're going to mark it as visited.
So we say visited at neighbors at I is equal to true.
So we mark it as visited and we're done.
Right.
So this is our function.
So once we are out of the while loop we just have to return the output array which we keep building
over here when we push the current value to the output array.
All right.
So that is it.
Now let's go ahead and test our function.
So we will call this function.
And we will pass this adjacency list to it.
And let's say we want to start traversing the graph at vertex A.
So let's go ahead and run this function.
And let's take a look at our output.
We get a f e c d b which is correct.
Right.
So this is the same graph which we used in our explanation video.
And we have seen that if we do a DFS search this is the output right.
So this is the output that we got when we discussed it.
And over here we have implemented it iteratively.
So let's now draw this graph.
And let's try to go ahead and look at the code and just walk through the code.
So let's go ahead and do that now.
All right.
So I have just drawn this graph over here so that we can visualize it.
Now let's try to trace the the code or walk through the code that we have written.
Now we are calling the function and we are passing this graph to it.
And we want to start traversing this graph over here DFS and iteratively.
And we start at vertex A.
So we are over here.
This graph has been passed to it.
And start is now vertex a.
So output at this point is an empty array.
So we have the output array over here.
So let's see how we get each element to it.
And then visited at this point is an empty object or an empty hash table.
And then we have stack right.
So let's just draw the stack over here.
So the stack at this point.
Has one element which is start.
Right.
So let me just write the stack over here we have start and start is a.
So this is how our stack looks at this point.
And we mark this as visited.
Right.
So A is visited.
So I'm just having a tick mark over here.
But this is going to be an entry in the hash table with the key A and the value as true.
All right.
So we come over here and we check whether there is something in the stack.
Yes there is an element.
So we come inside and we pop this element.
So we take out a and we push it to our output array.
So that is how we get a over here.
Now we find the neighbors of a right.
So for this we are going to make use of the adjacency list.
So we come over here and we see that the neighbors of A are B and f which is these two.
Right.
So now we are going to check over here whether they are visited or not.
We can see that they are not visited.
Right.
So only a has been visited so far.
So we push B and F to the stack.
Right.
And again over here A is already popped out.
So this is no longer there in the stack because we popped it out over here.
Now over here at this point we are pushing the neighbors B and F to the stack, and it's going to be
done in the order of storing it.
So we have stored B ahead of F over here in the adjacency list.
So we are going to push into the stack in this order.
So let's just write that over here.
So we are adding b and f these two into the stack because both of them are not visited.
And we will mark both of them as visited.
Right.
So that is happening over here.
In this part.
Right.
So we push them to the stack and we mark them as visited.
So that is done.
Now what we do, we come again over here and we see that the stack is not empty right.
So we pop from the stack.
So that means the stack is a data structure.
So we take out from the end right.
So we are popping.
So we are taking out F at this point.
So f is taken out and it is pushed to the to the output array.
So that is how we have f over here.
And then we find the neighbors of f.
So again for this we use the adjacency list which is passed to the function.
So the neighbors of f are a, b and e.
Now we check whether they are visited.
And we can see that A is already visited, B is already visited but E is not visited.
So we push E to the stack and we mark E as visited.
Right.
So this happens over here.
We pushed to the stack E and then we mark E as visited, which I'm denoting with this tick mark over
here.
And then again we come to the while loop.
We check whether the stack is empty.
We see that it is not empty, so we pop from the stack again.
Remember, we are taking from the end because the stack is a data structure.
Last in, first out.
So we pop, we take out E and we push it to the output array.
So we have E over here.
And again we are finding the neighbors of E.
And we can see that the neighbors of E are d, c and f.
Now D is it visited.
No it's not visited.
So what do we do.
We we push it to the stack.
So we have D over here and we mark it as visited.
The next one C is it visited.
No it's not visited.
So we mark it as visited and we push it to the stack.
The next one is um.
E uh, we are at E, right?
The next, the next one is f.
Now, F is already visited, so we don't push it to the stack.
So that is done.
So that happens over here right.
That happens over here.
We push to the stack and we mark as visited again we come over here we see that the stack is not empty.
So we pop.
We take from the n right.
So we pop C and we push it to the output array.
So that's how we have C over here.
Again we come over here and we take the neighbors of C.
You can see that the neighbors are B, E and d.
Again we use the adjacency list to find that.
And all of these are already visited.
So we don't add anything to this stack.
And that's it.
So we come over here again we pop from the end which is D.
And we push it to the output array.
So we have D over here.
We check the neighbors of D which is c and e and these are there or these are already visited right.
So we don't add anything to the stack.
And finally we pop B from the stack and we put it to the output array.
And the neighbors of B, A, F and c are already visited, so nothing is added to the stack.
Then when we come and check over here, we will see that the stack is empty and therefore we will come
out of this.
Right?
So we come out of this.
And at this point we will just return the output array, which is what we have over here.
So this is how our function works.
Now what about the space and time complexity.
Let's have a quick look at that.
So in this function we can see that we traverse or we visit every node once right.
So or we visit every vertex once.
So what is ensuring that it's this while loop over here.
Right.
So the stack this while loop over here will operate or will execute a number of times which is equal
to the number of vertices.
So we have the operations over there.
And then over here every at every vertex we will have operations equal to its neighbors.
Right.
So if we add up all these operations we will get two times the number of edges operations.
So this is the same thing that we have seen in the previous video where we did it recursively.
So that's why the time complexity over here is O of v plus e.
And the space complexity is going to be O of V.
Because what's the extra space that we're using.
We have this output array which is going to take space equal to the number of vertices.
We have the visited object over here, which will have key value pairs equal to the number of vertices.
And then we have the stack right.
So in the worst case this stack.
Also let's say this is a is also going to take space equal to order of V.
How is that happening.
Let's say you have a over here you have B over here C over here D over here E over here and F over here.
You can see in this case when we come over here and we start with a and we check its neighbors and push
the unvisited neighbors to the stack.
We will be pushing all of these elements to the stack.
So at that point the stack will have v minus one elements, which is of the order of V, right.
Because one is a constant and we can just remove it.
So that's why we can say that the space complexity is is of the order of a constant into V, and we
can just remove the constant and we get that the space complexity is O of V.