Welcome back.
Let's now code the breadth first search approach for this graph.
Now we will traverse this graph which is given over here.
And it's stored as an adjacency list.
Now we will traverse this using the BFS approach.
All right so let's get started.
So we will write a function let's call it traverse BFS.
All right.
So let's say const traverse BFS is equal to function.
And when we call this function we will pass the graph right.
So this is the graph the adjacency adjacency list.
So let's just call it graph.
And then we will also mention where we have to start.
All right.
Now over here inside this function we will have an output array right.
So that's the question right.
So let's just call it output.
And this will be an empty array.
And at the end we will just return this output.
So that's how we are going to do this.
And when we call this function we will have to pass this adjacency list and the starting point.
So from where do we want to start the BFS traversal.
So let's say graph BFS and we pass the graph uh or sorry over here it's called the adjacency list.
Right.
So we pass the adjacency list.
And let's say we want to start at eight.
All right.
So this is how we are going to do this.
Now let's get started with the function.
So once we are inside this so we have defined the empty array which will be the output.
Now we need an object let's call it visited so that we can track whether we have visited a vertex.
All right.
So let's call it visited.
And we also need a queue right.
So we'll need a queue const.
Let's just call it queue itself.
And initially itself because we are starting over here.
Right.
Whatever is the start which is passed to it.
So we can fill the start into the queue over here itself.
And whenever we are filling something into the queue, we mark it as visited.
Right?
So we can say visited at start is true.
All right.
Now we also need a variable.
Let's call it just current so that we can track where we are.
And I don't want to put it inside the while loop so that we don't initialize it again and again.
So over here we'll have the while loop.
And this will keep going as long as something is there in the queue.
Right.
So we can say while queue dot length is greater than zero right.
Or you can just say queue dot length also because zero as you know is falsy in JavaScript.
All right.
So while while queue dot length is greater than zero let's continue.
So what is it that we're going to do.
We are going to first we are going to shift or take from the beginning what is there in the queue.
So we can say current is equal to Q dot shift.
Now remember when you're implementing this in the interview you should mention that over here we are
implementing the queue as an array just to save time.
All right.
So the queue over here is implemented as an array just to save time.
Ideally you should be implementing it as a linked list to get the optimum performance.
Because over here you can notice that we are taking or we are removing an element from the beginning
of the queue.
So if we implement the queue as an array and if we do this over here, that's an O of n operation.
Right.
So it's not efficient.
So if we had implemented the queue as a linked list then that would be a O of one operation.
All right.
So let's proceed.
And remember queue is a Fifo data structure.
So we take out from the queue what was first input.
Right.
So what came in first comes out first.
All right.
So let's proceed.
So we have we take out the element from the beginning of the queue.
And then we push it to the output array.
So output dot push.
And then we say current.
So we push the current element to the output array.
Now once we are done with this we need to identify the neighbors of this current node.
All right.
So for this we will make use of the adjacency list or in this case inside the function.
It's called the graph right.
So let's say const neighbors.
And that will give us an array.
Right.
So it will give us the value over here.
You can see that in this list in this object actually the value is an array.
So this will give us an array.
So const neighbors is equal to graph.
And graph at current.
So we say current.
So we're going to pass current which is going to be a in this case in the beginning.
Right.
And later it's going to be one of these vertices.
So we will pass that that as the key.
And we get the value as this array over here.
All right.
So we say graph at current is neighbors.
Now once we are done this with this we need to loop through this array.
Right.
And we have to check whether that particular vertex in the array is already in the visited object.
If not we will push it to the queue.
So that's how we are going to do this, right as we discussed in the previous video.
So let's go ahead and implement this.
So for this I'm just going to write for let I is equal to zero.
Now as long as I less than neighbors dot length I plus plus.
All right.
Now, once we are inside this, let's identify what is the vertex at I at index I of this array over
here, right of these arrays at whatever particular array based on the key which you have passed in.
So over here we can say const neighbor.
Is equal to neighbors at I.
Right.
So this will give us one of these vertices.
Right.
So let's say we are taking this array.
We are we passed in a as the key.
We would have got this array over here.
Now when I is equal to zero we will get neighbor as b.
And when I is equal to one we will get neighbor as f.
All right.
So we got a neighbor.
Now we have to check whether this neighbor is there in the visited object or not.
Right.
So that we can know whether we have visited it or not.
So let's say if not.
If not visited.
Neighbor.
If so, that means it's not there in the visited object.
That means we have not yet visited it.
In this case, we have to push it to the queue, right?
So we say queue dot push and we push the neighbor to the queue.
All right.
Now once we have pushed it to the queue we have to mark it as visited.
So we say visited at neighbor.
And we have to mark that as true.
So this is equal to true.
All right.
And we are done.
Right.
So by this, uh, we come out of the while loop when there is nothing in the queue, and then we just
return the output array.
All right.
So let's go ahead and test it.
So we are we are calling the traverse function over here.
We are passing this graph over here which is stored as an adjacency list to it.
And then we are mentioning where to start.
So let's look at the output.
So I'm running this and you can see we are getting the output A, B, F, C, E and D.
Now let's quickly take a look at what is happening over here.
First let's analyze the output.
So over here I'm just going to write over here itself.
So let me just take a pen.
All right.
Now let's try to represent first this adjacency list as a graph so that it's easy for us to visualize.
So I have a so I have a over here and it's connected to B and F right.
So this is B and this is f.
Now I have B which is connected to A, so we already have that connection.
Then B is connected to F and C.
So we have b and f and b and c.
Now we come to c c is connected to B which we have already have over here.
And c is connected to E and D.
So let's just call it e over here.
And I have D over here.
Now we come to D d is connected to C and d is connected to E.
So we make this connection.
And when it comes to e is connected to D.
And e is connected to C which we already have and e is connected to f.
So we make this connection and f is connected to a, f is connected to b, and f is connected to E,
which we already have.
So this is our graph.
And we started to traverse it from a right.
So we passed in a.
So let's check what's happening in the code.
So let me just expand this a little bit.
So we have our output over here and we have the graph over here.
So I'm just taking the function into view.
All right.
So let's continue.
All right.
So let's proceed.
So when we have called the function we are over here and we have passed the adjacency list which is
this over here.
And the start.
So we are starting at a.
Now we have output which is empty.
So let's this is the output.
All right.
So output is empty.
And we have visited which is also empty.
So let's just track it over here.
So I have visited over here and visited is empty.
And we have the queue.
So we have the queue.
This is the queue.
And we push the start right.
So a is put into the queue at this point over here.
Right.
Cons queue is equal to start.
So we have already the starting point in the queue.
Now we are saying visited start true.
So we are saying a and then we are giving the value true to it.
So A is visited at this point.
Now we are over here, we see that the length of the queue is greater than zero because we have this
element over here, right?
So we come over here and we take the first element out.
So we take this out and we put it into the output.
So we put it over here.
All right.
Now we are going to check its neighbors.
So we are going to check the neighbors.
And for this we are making use of the adjacency list.
So let's just look at that for for a moment.
So we are looking over here, right?
So we can see that the neighbors of R, B and F over here, neighbors will be equal to this array over
here B and f.
Right.
So again visually we can see that we are getting b and f which are the neighbors of A.
Similarly when we have b we will get this array over here right which is a f.
And see this a f and c.
Right.
So those are the neighbors of B.
So over here neighbors is going to give us uh the neighbors of A.
All right.
So let's proceed.
Uh, wait, let me just bring that back.
So we need this over here, right?
So let's continue from where we are.
I'm just, uh, uh, clearing up a little bit of what we've written so that whatever is not clear,
because I've shifted this, so that doesn't confuse us.
So let's continue.
So we have taken we are now over here.
Right.
We have we have got the neighbors of A now for the we are getting this array right B and F.
Let me just write that over here so that we are very clear what we have.
So we got B and F.
So I'm just writing it over here we have this array b comma f.
All right, now let's proceed.
Um.
This is.
Come back.
All right.
So we have the neighbors.
Now for I is equal to zero I less than neighbors dot length.
So the length of neighbors is two over here.
So I is equal to zero and I is equal to one.
For these two values the for loop will run right.
So we take the neighbor.
So we get first the neighbor as b and we are checking whether B is there.
In visited we see that it is not there.
So we put so what do we do.
We push it to the queue.
So we put B to the queue.
So we have B over here.
We put it to the queue and then we mark it as visited.
So we have B as visited also.
And then what do we do again.
We come when I is equal to one right.
So again we check whether f is there, f is not there, f is not there in visited.
So we push it to the queue.
So we have f over here.
And then uh we mark f as visited.
So I'm not writing.
True.
I'm just writing the element over here.
And then we are out of the for loop.
And again we come to the while loop over here.
All right.
So once we are over here again we are checking whether there is something in the queue we see.
Yes it's there.
So we have B and F in the queue.
Right.
So we we take the element from the beginning.
So we take B out and we put it over here which is the output array.
So output dot push current.
So we get B over here.
All right.
Now we are checking the neighbors of B.
So similarly when we check the neighbors of B we will get an array a f and c right.
So let's take a look at that over here.
Let's just go up.
So we have a F and c.
So let me just write that over here.
Uh.
All right, so I'm just removing this.
All right.
So the array that we are getting over here is f f and c.
So that's the array we have.
Now let's come back.
All right.
So.
We are again inside the while loop.
So let me clear this up.
Okay, so we are inside the wire loop a while loop.
So we are over here and uh, we, we took B, we pushed it to current.
And then over here we are checking the neighbor.
So we got a F and C as the neighbors of B.
So inside this we are going to loop from I is equal to zero one and two.
Right.
So the length over here is three.
So now first we take the first neighbor which is a.
We see that it is already there in visited.
So we don't push it to the queue.
Then we check the next neighbor which is F we see it's there in the visited.
Right.
So we don't, uh, process this.
Then we come over here and we see that visit C is not there in visited.
So we put it into visited and we put it to the queue.
Right.
So we put it to the queue and we push it, put it to visited over here.
And then we come out.
Right.
So we come out of this for loop and again we, we see that yes, we have stuff in the queue.
So what do we do.
We take the element from the beginning and we push it to the output.
So we have F over here you can see that we are building the output a, b, f.
That's what you're getting over here a, b.
And then we got F right now again we come uh again we come over here we have we are now at the neighbors
of F.
We see that the neighbors of F are A, B and E, right.
So again we will check whether A is there in visited.
It's there B is also there.
So only E is not there.
So what do we do.
So if E is not there we put it to the queue.
So we get E over here and we mark E as visited.
So we have E also as visited.
Again we see that there are, there is, there are things in the queue.
Right.
So let me just take another pen.
So over here we shift.
So we take the first element and then we push it to the current element.
So we have C over here.
Now we check the the neighbors of C.
So the neighbors of C are b D and E right.
So we can see that we already have b and e in visited.
So only d is remaining.
So we put D to visited and we push it to the queue as well.
Right.
So again we see that there are there is things in the queue.
So again we are, we are, we are over here.
So again we come into the while loop.
We take the current element which is the beginning from the beginning of the queue.
Right.
So all of these are already out.
So only E is at the beginning.
We take it from the queue and we put it to the output.
And then we are going to check the neighbors of E which is C, D and f and C, D and f are already there
in visited, so we don't add anything to the queue.
Again we come over here, we see there is still one element in the queue.
So we take it out, we shift it and we put it to the output.
Right.
We push it to the output array.
And then for the neighbors of D, C and E are already there.
So we don't add anything to the visited or um, object or to the queue.
And we are done.
So we come out and we just return this array over here which is A, B, F, C, E and d, and that is
our output.
Now when it comes to the time and space complexity, we can see that over here we are.
What are the things that consume space?
So one is this visited object.
And then we have this output array.
And then we have this queue.
So these are the things that take additional space right.
So you can see that the space complexity is O of V right.
Which is the number of nodes.
Again over here we have v elements in this array.
Even if we were not asked to give the output as an array.
And suppose we were not building this even then.
Over here you can see that our visited object consumes V space, right?
And the queue also the.
In the worst case, as we have seen in the previous video, it can take up to v elements, right.
So in that case also this also could consume v space.
So the space complexity of this solution is O of V.
And what about the time complexity.
The time complexity of this solution is O of e plus v.
Right.
So why is that.
So now over here you can see that we are visiting every node once right.
So or every vertex once.
So that's why we have v over here which is every vertex.
And then when we have this for loop when we are checking the neighbors.
Actually the neighbors of A are actually these edges, right.
So the neighbors of A is a and b f and b.
So that's indicated by these two edges.
So again when we check the neighbors of c for example we go to b d and e right.
So those are these edges right.
So the um the time complexity over here will be a multiple of the number of edges which we have.
So that's why we get that the time complexity of this solution is O of e plus v.