Hi everyone.
In this question we are going to see how we can implement depth.
First search for a graph.
Now over here we are going to do it in both the ways we can either do DFS recursively or iteratively.
So let's read the question.
You are given a graph stored as an adjacency list.
Write functions to traverse the graph using the depth first search approach recursively and iteratively.
So we are going to do it in both the ways.
As you traverse the graph, store the values of the vertices in an array and return this array.
So let's go ahead and do this.
And notice that over here it's given that the graph is stored as an adjacency list.
So let's say this is the graph that we have.
And this would be stored in the adjacency list in this manner.
Right.
We have all the six nodes over here.
And then we have an array over here for each key where the array is the value.
And this value over here is the neighbors right.
For example A has the neighbors b and f.
That's why this array over here has b and f.
All right.
So we have already seen this previously.
Now let's go ahead and understand DFS first.
And then we will see how we can implement this in our code.
All right.
Now the idea of DFS or depth first search or depth first traversal is that we visit a child node before
we visit the neighbor of a particular node.
So what does this mean.
So let's try to understand this.
Let's say we start traversing this graph over here at this node over here which is node A or vertex
a.
Now we go to its child.
So the child of A is b.
All right.
So we go to the child and then we again go to the child of B.
Right.
We could have gone to the neighbor.
The neighbor of B is F right.
So that is what we did in the case of BFS or breadth first search.
But over here we have to go to the child before the neighbor.
So that is why we go from B to C which is the child of B, right.
And after that we go to the child of C which is E, right.
So I could have gone to D also.
But in this case we are going to choose the child based on how it is stored.
And you can see that in this, this array over here we are, we have e before D right.
So B is already visited.
So we are not going to go back.
But of the child of the children of C we have D and E, but because over here we have stored e before
D that's why we go e first.
So if we had stored D before E we would have gone D first.
So that does not matter.
So we go to E and then from E we are going to go to its child which is D right.
Again over here you can see we have D first right.
So that is why we are going to D before we go to F.
Now we see that D does not have any unvisited child.
Right.
So it does not have a child to visit.
That's why we are going to visit the neighbor.
So there is no child.
So we go to the neighbor.
So the neighbor of D is F right.
So the neighbor of D is f because d is a child of E, right.
So d is a child of e at this point.
Right.
So this is done.
And then f is the neighbor of d.
But first we try whether we have a child of d.
So in this case we don't have.
That's why we go to the neighbor of E which is f.
So we go in this direction.
And at this point you can see we have traversed or visited all the nodes.
And if we were to print all the values as we visited the different nodes into an array, it would look
like this a and then from A we went to B.
From B we went to C, from C, we went to E, from E we went to D, and then from there we went to F,
which is the neighbor of E, right.
Because D did not have any child.
So this is how depth first search works.
So we go as deep as possible before we start going wide.
So that's the idea.
Or we visit children before we visit neighbors.
All right.
So that is DFS.
And then another important thing to keep in mind is there is no unique DFS for a given graph.
Right.
So there would be nothing wrong if instead of going from C to E, if I had taken the choice of going
from C to D, and again, we made that choice based on how we had stored the different children in this
array over here.
So the important thing is there is no unique DFS for a given graph.
The the the output array which we are getting in this case depends on the choices that we have made.
So we can have many answers if you do a DFS for a particular graph.
All right.
So let's now go ahead and see how we can implement this.
First we will try to implement this recursively.
So let's go ahead and do this.
We are going to implement DFS recursively.
Now for this we will need a function.
So let's call this function f.
And we will be calling this function recursively for every node.
Now initially let's say we are calling this function for the node a and we have to pass the graph to
it.
And we also need to pass an output array to it.
And we also have to have a visited object or a hash table to see whether we have visited a particular
vertex or not.
All right.
So let's say we initially call this function and we have it in our call stack.
So we have to graph with vertex A in our call stack so that we will keep tracking the call stack also
over here so that we get an understanding of the recursive function.
All right.
And again we need an output array which we have over here.
Initially the output array is empty and the visited object is also empty.
Now at this point we have called graph with vertex a.
All right.
So we are inside the trial function.
And what we will do is we will push that value to our output array.
And we will mark it as visited.
So we have visited A and we have pushed it to our output array.
All right.
Now what we do is we will try to identify the neighbors of this particular vertex.
All right.
So the neighbors of A are b and f.
And for this we make use of the graph which is stored as an adjacency list over here.
So we take the neighbors.
And if a particular neighbor is not yet visited we will recursively call the function passing that particular
neighbor vertex.
So this is how this works.
So at this point we have b.
We see that it is not yet visited.
So we will call the try function recursively for b.
All right.
And once we are and again this is a DFS right.
So we will go depth first.
But once we come back to this level we have still an option to call the trial function for F as well.
Because at this point f is not yet visited.
So I'm just writing F over here so that we can visually track the recursive call.
All right.
So it so that it does not get confused.
So when we come back the idea is that if f is not yet visited then at this point we will call f again
with f vertex f at that point.
All right.
So at this point we are again back over here.
And vertex at this point is b.
Now we push b to our output array and we mark B as visited.
And then we are going to identify the neighbors of B at this point.
Right.
So for this we make use of the adjacency list.
And we see that the neighbors are A and C a is already visited.
So we are going to call recursively the trial function for vertex c.
So that is traffic c at this point.
All right.
So we come again over here.
Now at this point when we are at this line we are going to push C to our output array.
And we will mark C as visited.
And then we are going to identify the neighbors of C which is B, E and D.
And among these b is already visited.
So e and D are not visited.
Right.
So we are going to call f function this trap function recursively with e and we have the option to call
it with d.
So again this is DFS.
We go depth first.
But once we are back over here if D is not yet visited then we have the option to call the trap function
with D at that point when we are coming back.
All right.
So we call trap with E again.
We come inside the trap function.
We are going to push E to our output array and we mark E as visited.
Now we are going to identify the neighbors of E which is D, C and f.
Now among this we can see that only c is visited, right.
So we can call the trap function for d and f.
So we first call it for d.
And then we have the option to call it for f.
So I mark F over here.
And then again when we do that we push D and we mark D as visited.
And then we are going to check the neighbors of D.
So the neighbors of D are C and E.
And you can see that both of them are visited.
Right.
So no recursive call is going to happen.
So this call where we call the function passing D is done right.
So this is done again there is no neighbor which is unvisited which we checked over here using the adjacency
list.
So at this point this call is over right.
So this was done where we pushed D and marked it as visited.
We identified the neighbors of D and then we checked for the neighbors.
If they were not visited we saw there is none which is not visited.
So this call is over right.
So this call is over and the call stack is cleared.
Now we come back over here.
We had the option to call for F as well.
Right at this point where we were checking for the neighbors of E.
So we are done with this.
And C is already visited.
Now we will iterate to f, we see that f is not yet visited.
So we will call trough with f.
So we call trough with f at this point.
So we are again inside the trough function.
We push f to the output array and we mark f as visited.
All right.
So that is done.
And that brings us to the end of this call as well.
So this is also done right.
Because all of these neighbors A and D are already visited.
So this is not going to execute.
So that call of trough is done.
So we return right.
So f is done D is done and we come back over here.
So at this point the call the depth first call from here is done.
So this is also done right.
So we have the option now to increment and go to D.
But we can see that D is already visited at this point.
So we are not going to call D again.
Right.
We are not going to go with D.
And then this call is done.
Right.
So this was part of the this going deep was part of this call traffic.
Right.
So we were checking the neighbors of C.
So the neighbors of C are done now right.
So this call is also done.
It returns.
And then this call is also done because this call was part of B call.
So all of this is done.
So B is done.
We have the option to call the trial function with f.
But we can see that f is already visited.
So this does not happen.
And then we come back and this call is also done right.
So we come out of the call stack.
So the call stack is empty at this point.
Again why is this out.
Because we pushed a and then we checked for the neighbors of A which is B and F.
And then we went depth first.
Right.
So we took the child which is B and we went in this direction.
So when we come back we see that f is already visited.
So that's why when we got back to here we are not going to call the trap function with f.
So once this step is done, this step is done and this step is done right.
So that was checking the children and if not visited calling the trap function recursively.
So that is also done.
So once this is done this call is done right.
So this call was with vertex A.
So this is also done.
So that's why trough A is removed from the call stack.
So the call stack is empty and we're done.
So we get our output array which is a b c e d and f.
So this is how the DFS recursive function works.
Now let's take a quick look at the complexity analysis of this solution.
Now the time complexity of this solution is going going to be of the order of v plus E where v is the
number of vertices and e is the number of edges.
Now why is this.
So we are traversing or visiting every vertex once right.
So for this we have v over here right.
So we are traversing every vertex at least once.
So we have to do v operations.
Or we can say that we have to call the travel function v times right.
For each vertex we have to call it at least once.
So we have to call it once exactly for each vertex.
Right.
So we are doing v operations over here.
And then over here when we are checking whether the neighbor is visited or not.
So we are doing this two e times.
Right.
We are doing it two e times because for every vertex we have to do it the number of times equivalent
to the size of the array for that particular vertex.
So if we add all of these up what is it that we are getting.
Let's try 123456789 1011 1213 and 14.
So this over here is going to do 14 operations.
And this 14 is nothing but two times seven where seven is the number of edges.
So that is why we can say that the time complexity is of the order of V plus two e.
You can say two e over here, but then two is a constant.
So we can just avoid that.
And we get that the time complexity is O of v plus e.
Again remember the for loop is operating as many times as the number of children, which is nothing
but the number of edges over here.
Right.
So again we have to check whether it is visited or not.
Even though it's visited, we still have to check when we encounter a particular node again, we have
to still make an operation and see whether it is visited or not.
So the number of operations which is happening over here, across all the calls is equal to two e.
And then we remove the constant two.
That's why we get that the time complexity over here is of the order of V plus e.
Now, what about the space complexity?
The space complexity over here is going to be of the order of V.
Why is that so?
What are the different things that consume space?
Over here we have the output array right which will have v elements.
We have the visited object which also will have v number of key value pairs.
And then we have the call stack right.
Even the call stack in the worst case is going to take order of v space.
Right.
So again even if we did not want the output array then also the space complexity will be O of V because
we have the visited object.
And then even if you just look at the call stack in the worst case.
And remember whenever we have a big O analysis, we are giving the worst case, right?
So the call stack in the worst case will look something will look something like this for an array.
So for a graph that looks something like this where a is pointing to b, b is pointing to c, C is pointing
to d, d is pointing to e, and e is pointing to f.
So if this is the case, then when we start from a we will go all the way till here.
Right.
So the call stack in this case will have v number of calls.
Right.
So in this case the call stack also will take O of v space.
That's why we can say that the space complexity of this solution is O of v into a constant.
Right.
And then we just remove the constant and we get that the space complexity is O of V.