Welcome back.
Let's now see how we can implement the DFS or depth first search algorithm iteratively.
So we have our graph over here.
And it is stored as an adjacency list.
Now to implement the DFS algorithm iteratively we will use a stack.
Now a stack is a lifer or last in first out data structure.
So initially our stack is empty.
And let's say we want to start to traverse the graph at vertex A.
So we are starting over here.
Now what we will do is we will push this to our stack.
So let's have it in our stack.
And we also need an output array.
So let's say this is our output array which is empty at this point.
And then once we push a to our stack we will mark it as visited.
So A is now visited.
And what we will do is we will have a while loop.
So this is the difference between BFS and DFS when we implement implemented iteratively.
Now again we have a while loop similar to the case of BFS where we check if something is in the stack
and as long as something is in the stack, we will keep looping.
So this is our while loop.
Now at this point we have something in our stack.
So we will pop from the stack and we will push it to the output array.
So this is the difference.
All right.
So in the case of BFS we had a queue.
And a queue is a Fifo or first in first out data structure.
So we used to take from the first or from the beginning.
Right.
But over here we're going to pop right.
So we are going to take from the end of the stack.
So this will ensure that we get children before neighbors.
So let's trace the algorithm and this will become more clear.
So at this point it just has one element.
So we pop A and we push it to the output array.
So we have a over here.
And then we are going to check the neighbors of a.
Right.
So the neighbors of A are B and f.
And to check this we use the adjacency list.
Now we are going to check whether these are already visited.
And if not we will push them to the stack so we can see that b and F as at this moment are not visited.
So let's push b and f to the stack.
So we get B and f over here.
All right.
And we mark them as visited.
Now again we are over here and we check if the stack is empty.
No it's not empty.
So we come inside the while loop and we are going to pop.
So popping means we are going to take the last element right which is F at this point.
And this will help us get children before neighbors.
So we are going to take f, we are taking from the end of the stack because the stack is a leaf, right
last in first out data structure.
So we take out F and we push it to our output array.
And we are going to check the neighbors of F, which is A and E.
Now you can see that A is already visited, but E is not visited.
So we push E to the stack and we mark E as visited.
Again.
We come inside and we are going to pop from the stack.
That is, we are going to take the last element which is E at this point.
So we take E and we push it to the output array.
And then we are going to check the neighbors of E which is D, C and f.
Now among these we can see that, uh, none of them are visited.
Right.
So d c and f okay f is visited.
So we have f as visited, but d and C are not visited.
Right.
So again at this point we are going to push d and C to our stack.
So let's do that.
And we mark D and C as visited.
And again we check whether the stack is empty.
No it is not empty.
And we are going to pop.
So we come inside the while loop.
And we are going to take from the end.
Right.
So it is this that makes this DFS right depth first because we are always taking from the end of the
stack.
So we get children before neighbors.
So at this point we are going to pop.
So we get C and we push it to the output array.
And we are going to check the neighbors of C.
We get b, E and d, we see that B, E and d are already visited, so we don't push anything to the
stack.
So we come again to the while condition.
We see that the stack is not empty, so we pop from the stack, which is D.
At this point we push it to the output array.
We check the neighbors of D, which is C and E and C and E are already there, so we do not push anything
to the stack.
And after that again we check whether the stack is empty.
No, it's not empty.
We still have one element.
So we pop that and we push it to our output array.
We check the neighbors of B, which is A and C and A and C are already visited.
So that brings us to the end, because when we come again and check over here, we will see that the
stack is empty and we are done.
And this is our output array which is a f e c d b.
So you can see that DFS iteratively is implemented using a stack.
So what we do is we start somewhere.
We push it to the stack, we mark it as visited and we check its neighbors.
So if there are neighbors which are not visited we push it to the stack.
Right.
But then when we again come over here, we always pop or we take from the end of the stack, which will
ensure that we get children before neighbors.
And that is the depth first search.
All right.
Now let's quickly take a look at the complexity analysis of this solution where we are doing DFS search
iteratively.
Now the time complexity of this solution is of the order of V plus E, where v is the number of vertices
and e is the number of edges.
Now the time complexity is O of v plus e, because over here we have this while loop right.
So this while loop will operate a total of v number of times one time for each vertex.
So we have v operations over here.
So this is used to traverse every vertex right.
And then inside we pop and we push it to the output array.
Now over here we have E because of this for loop over here where we use it to check whether it's the
neighbors of that particular vertex is visited or not.
So you can see that we will iterate for every edge of the vertex, right.
Because we use the adjacency list.
So for example, if we are at vertex A we will do two checks for b and f to see whether it is visited
or not.
Similarly, over here also we will do two checks.
Now if we add all of these together up all of these operations together, we will get a total of two
into E number of operations.
So we can say that the time complexity is O of V plus two E because two is a constant, we can just
remove it.
And we can say that the time complexity is of the order of V plus e.
Now what about the space complexity?
The space complexity of this solution is of the order of V.
Now what are the things that take extra space?
We have the visited object, we have the stack, and then we have the output array.
Right now, even if we did not want an output array as per the question, let's say we modify the question
and we don't want to output the traversed path as an output array.
Even in that case, the space complexity would be of the order of V, because we have this visited object
which will have v number of key value pairs.
And then we have this stack over here right now in the worst case.
And again when we do a Big-O analysis we always give the worst case.
Right.
So in the worst case what's the stack going to look like.
Let's take a look at that.
Let's say the graph is something like this where A is connected to B and it's connected to c, d, e
and f.
So in this case when the current vertex is a and we visit the neighbors and push the non visited neighbors
to our stack, all of these would be pushed to the stack, right.
So that would be a total of total of V minus one number of elements in our stack.
And one is just a constant.
So we can avoid that.
And in this case we can see that the stack also takes O of v space.
So we can see that the space complexity of this solution will be O of a constant into V, and we can
just remove the constant.
And we get that the space complexity is equal to O of V.