Welcome back.
Let's now go ahead and write the function that will traverse this graph depth first.
And we are going to write a recursive function over here.
So let's call this function Trav DFS.
Now this function is going to be recursively called.
So we have to decide what parameters should be passed to it at every point.
So we definitely need the graph which is this adjacency list over here.
And we need the current vertex where we are at when we call this function.
And we also need the output array which is to be returned.
Finally.
And we need a object let's call it visited, so that we can keep track of which nodes or vertices have
been visited so far.
All right.
So at this point, once we are inside this function we will have called it with a particular vertex
right.
So initially itself we will push that to the output array.
So we can say output dot push vertex.
And we will mark that particular vertex as visited.
So we can say visited at vertex is true.
All right.
Now we are going to find the neighbors of this particular vertex.
And if they have not been visited, then we will call DFS function recursively for those particular
vertices.
So let's go ahead and do that.
So we can say const neighbors.
Is equal to this.
This we have this adjacency list is the graph that is passed to over here right to this function.
So we can say the neighbors is graph.
At vertex.
All right.
So for example if we have the vertex a then we will take the values where the key is a in this adjacency
list which is b and f.
So this array will be neighbors.
So this neighbors is going to be the array of the neighbors of that particular vertex.
Now we are going to loop through that array.
So let's have a for loop for let I is equal to zero I less than.
Neighbors dot length.
I plus, plus.
All right.
Now we are going to identify each neighbor so we can say const neighbor.
Is equal to neighbors.
At I.
So this is going to be one particular neighbor.
For example, B is a neighbor.
Right now we have to check whether this neighbor is there in the visited object.
So let's do that.
So if.
Not visited at neighbor.
Right.
So if this is undefined, that means there is no entry where the key is equal to the neighbor.
If this is the case, then we will recursively call the DFS function.
So again trav dfs.
And then we have to just pass the parameters.
So we have the graph.
And at this point the vertex is going to be this particular neighbor.
So over here we say neighbor.
And then we have to parse the output array and the visited object to keep track whether we have visited
a vertex or not.
And that is it.
So once we are done with this, once we are out of this for loop, we have to just return output.
And we are done with our function.
Now let's test it out.
So we have the adjacency list over here.
So let's call this function.
Travis.
And let's take a look at the parameters.
We have to pass the graph, which is the adjacency list which we have over here.
This is given to us as part of the question.
And let's say we want to start traversing the graph from vertex A and the output array.
At this point let it just be an empty array.
And the visited object is also just going to be an empty object.
So that is it.
So this should work.
So let's try run our code and let's take a look at the output that we are getting.
All right.
So we are getting a, b, c, e d and f okay.
So this is working.
So this is the same graph which we discussed when we discussed the concept video.
But let's over here take a moment and relook at the code.
And we will also quickly take a relook at the space and time complexity.
So for this let me just draw this out so that we can visualize it better.
All right.
So I have drawn the graph over here so that we can visualize it.
Now let's try to trace the algorithm and let's see what's happening.
Initially we call DFS and we are passing the vertex a and the output array is empty and the visited
object is empty.
So we come over here and we are going to push a to the output array.
So that is why we have a over here.
All right.
And then we mark A as visited.
So let's just make a tick mark over here to indicate that A is visited.
Now we are going to identify the neighbors of A which is B and F.
And we are going to have this for loop where I is going to take the values zero and one, because the
length of neighbors is two.
Right?
So and then for each of these neighbors, which is b and f, we are going to check whether they have
been visited or not.
And if not we are going to recursively call Trav DFS.
So initially we are going to call it for B.
So let me just keep track of that over here.
So we are going to call Trav DFS for B.
All right.
And later we have the opportunity to call it for F also.
So I'm just keeping it over here so that we can see what's happening.
Right.
So this is the recursive call stack.
So we are calling DFS where we are passing B.
Again we come over here.
And at this point we push b to the output array.
So we have b over here.
And we mark it as visited.
So let's have a tick mark.
And after this we are going to check the neighbors of B which is A and C.
Now again I is initially C zero.
So at that point we get the neighbor as a right.
This this line over here const neighbor is neighbors at I we get the neighbor as a but we see that it
is already visited.
So we don't call the DFS function for A.
And then we go to the next neighbor.
All right.
So let me just make some space over here.
All right.
Let's just make it a little bit smaller.
So let's continue.
So I take the next neighbor which is C right.
So the next neighbor is C at this point.
And we can see that C is not yet visited.
So we call DFS and we pass C.
So let's do that over here.
Let me just have C written over here and then there is nothing else.
Write.
The neighbors are just A and C, and for A it was already visited.
So we did not call the DFS function.
So we call it for C.
And we come over here and we push C to the output array.
So that's what we have over here.
And after that we mark C as visited.
And we find its neighbors which is B, e and d.
So among b, e and d b is already visited, e and D are not visited.
So we take the.
When I is zero, we get B, but we don't call the function for that because it's already visited.
Then when I is equal to one, we get E right?
So we're going to recursively call the DFS function again over here.
And vertex is going to be e at this point.
And later we have the option to call it for D right when I becomes two.
So I'm just writing that over here.
So we are calling DFS with E.
Again we come over here we push E to the output array.
So we have that over here.
And we mark E as visited.
So I have a tick mark.
And then we are going to identify the neighbors of E which is D, C and f.
Now among this d is the the node that we get when I is equal to zero.
And we see that d is not yet visited.
Right.
So we are going to call DFS with D right.
And then we have the option to call it with C.
Do we have.
No.
It's already visited.
So we don't have the option over here.
And F is not yet visited.
Right.
So let me just write that over here.
We have the option to call DFS later with F when I is equal to two.
That will happen later.
So at this point we are calling it with D.
So again we come over here we push d to the output array.
So we have D over here.
And we mark D as visited.
We identify the neighbors of D, which is C and E, and both of them are visited.
Right.
So in this for loop we do not call DFS and we come out right.
So this call is over.
Now once this call is over remember we had the option to call it with F also.
Right.
So for the neighbors E right we had d c and f.
So for D it's done.
See it was already done.
Now we call it for f.
So we call DFS for f which is this one over here.
And we come over here.
We push f to the output array.
So we have f.
You can see that over here.
Right.
We have F over here, so we push it to the output array.
At that point we mark F as visited.
So let's have our tick mark.
And after that, we are going to identify the neighbors of F over here.
Which is A and E, and both of them are already visited.
So in this for loop we will not call the traverse recursively and this function is also done.
So this is done.
So d is done and f is done right.
So this was part of the call where we had e right.
So it was recursively calling it where the function was called with vertex e.
So that part is done.
And we have the option to call it with d.
But we see that it is already visited, so we no longer need to visit it.
And again C and B and F are already visited.
Right.
So we have already visited visited them B, C and F.
So again these things this is not going to again call.
And these are returning.
And they will will be out of this.
Right.
So yes we got our output a b c, e D and f.
So this is how our function works.
Now what about the time complexity.
The time complexity over here is O of v plus e right.
Why is that.
So let's take a look.
So over here we can see that we are going to visit every node.
Right.
So we are visiting every node.
That means traverse will be called for every node that is V operations.
Now for each of these operations we have this for loop which will run for operations equal to its edges.
Right.
For example, when we call traverse with vertex a, this for loop there will operate two times.
For I is equal to zero and one because the length over here is two right.
So I has to take the value zero and one.
Similarly, when we have the vertex b passed to it, this for loop will run two times.
So in this way we can see that the for loop will run for a total of two into the number of edges.
Let's just count that 123456789 ten 1112 1314.
Right.
So the for loop will operate for 14 times.
And you can see we have one, two, three, four, five, six and seven.
We have seven edges.
So this 14 is nothing but two into edges.
So we can say the time complexity is O of v plus two e.
Now because two is a constant we can just remove it.
That's why we get that the time complexity is O of v plus e, and the space complexity is O of V.
Right.
The space complexity over here is O of V.
Why is that so one we have the output array which will be of length v which is the number of vertices.
Right.
And then we have this visited object.
This also will have v number of key value pairs.
So this is also taking space of the order of v.
And then over here we have these recursive calls right.
So in the worst case we can have v calls in the call stack.
So what would be the worst case.
Let's say the graph looked like this a b c, d, e and f.
Right.
So from eight will will go to B.
From B we will go to C.
From C we will go to D and from D to E and from E to F.
So this is the worst case where we will have v calls on the call stack.
So we can say that the space complexity is of the order of a constant into the number of vertices.
And we can just remove the word constant.
And therefore we get that the space complexity is of the order of V.