Hi everyone!
Now let's code the BFS traversal solution for this matrix over here, which is given or which is stored
as an adjacency matrix.
So over here we have the relationships right whether there are connections or not.
And you can see that this is just a two dimensional array.
And over here notice that we have an array where it's mentioned as vertices.
So this will give us the vertices and the particular index where the vertex is.
For example we have vertex b at index one right zero one.
So that's how we know that this over here is the connections which are there from B.
All right.
And then we have the object over here which is called vertex indices.
Now we have this object so that we can get this index.
That is the index of b is equal to one, the index of e is equal to four etc. without always having
to traverse this array over here.
And that will help us to have a better time complexity for our solution.
Right.
So we just want to know the index of a particular node with constant time.
So that's why we have this object over here.
All right.
So let's now go ahead and code the solution.
So we will have a function let's call it BFS itself.
So we have to have BFS and that's equal to function.
And we will be passing in the graph.
All right which is that adjacency matrix.
And then we will say where to start.
All right.
So inside this function we will create an array.
Let's call it output.
So this will be an empty array right.
So let's say const output is an empty array.
And then finally we will just return this array over here.
All right.
So that's what we are trying to do.
So return output.
And then we will just call the BFS function over here.
And we will pass the adjacency matrix.
And we will mention where we want to start traversing it.
So this is what we are trying to do.
Now let's go ahead and complete this function over here BFS.
So we also need a visited object to track whether we have visited a node or not.
And we will also need a queue.
Right.
So let's say const queue is equal to.
And then as we are starting at this right we are passing start a.
So we know that we want to start traversing the graph at that node or that vertex.
So we can pass it to the queue over here itself.
Now whenever something is added to the queue, we mark it as visited.
So we can say visited at start.
Is equal to true.
All right.
Now we will have a while loop.
So as long as something is there in the queue, we will keep looping through the while loop again and
again.
So while queue dot length greater than zero that's the condition.
And again let me just have two variables over here.
Let's call it current and current index.
Right.
So current will be the node that we are taking out at every point from the queue.
And then we need to know its index right, which we will find using the vertex indices over here.
Right.
So we can find it, find its index so that we can immediately know at which um row we should take.
Right.
For example, if we take it as zero one, two three, if we if we have the node which is D, then immediately
we get that the index is three.
And then we can come over here 0123.
And we get this array over here which represents its neighbors.
So that's why we need current index over here.
All right.
So while queue dot length is greater than zero that means as long as something is there in the queue.
And again remember over here we have implemented the queue as an array just to save time.
So you need to mention this to your interviewer.
Now ideally we should be implementing it as an as a linked list to get optimum time performance.
Right.
Because we are removing elements from the beginning of the queue and removing something from the beginning
of an array is an O of n operation.
But if we had implemented this queue as a linked list, that would be a constant time operation.
All right.
So let's come back to this while loop over here.
Now while something is there in the queue, what we will do is we will say current is equal to q dot
shift.
So we are taking the first element from the queue.
Now we are going to push this to our output array.
So output dot push and let's just push current to it.
All right.
Now we are going to check its neighbors.
Right.
So for this we need to know the index.
So current index is equal to vertex indices at current.
Right.
So we are using this object over here.
We are passing the, the uh node A, B, C etc. as key over here.
And we will get the index back as value.
So that's what we have done over here.
So we get the current index.
Now we can just take its neighbors right.
So we can say const neighbors which will be an array.
Right.
So neighbors.
Is equal to.
Graph.
Current index.
All right.
So we will get one of these graphs, one of these arrays right as its neighbors depending on what the
index is or what the node is which where we are at currently.
So we get the neighbors.
Now we have to loop through the neighbors and see whether it's already visited.
And if not, we have to push it to the queue.
So that's what we are doing over here.
So for this let's use a for loop for let I is equal to zero I less than neighbors dot length.
And I.
Plus, plus.
All right.
So we are looping through it.
And now let's say that we want to check whether the value is one or not.
Right.
So if there is a one then only we need to be concerned with that particular neighbor because a one indicates
that yes, that particular node has a neighbor.
And again it depends on where it is.
Right.
For example, over here, if we have a as the current node, then this is the array that we would have
got as neighbors.
Now we see that there is a one over here.
So at this point I will be zero one right I will be one.
So I is equal to one means that's node B because we know the um the indices over here.
Right.
So this is zero.
This is one.
So we know that A has a connection with B.
So that's how we make that connection over here.
We have to check whether neighbors at I is equal to one.
So let's do that.
If neighbors at I if this is equal to one and if it's not visited right.
So we have to know whether it's visited or not.
So not visited.
And over here we cannot pass the index.
Right.
So over here neighbors I will be just 0 or 1.
And I will give us the index.
Right.
This is the index of 012345 which is the same index as we have for this vertices array 012345.
But we cannot just but in the visited array like in the visited object over here we are.
We are not passing the index right.
We are passing the the node the value.
So we need to check whether visited.
So for this we have to use vertices this array over here vertices right.
So if we say vertices.
Which is an array at I.
So that will give us, for example, if the index is two, as we saw over here, we see that we have
the index is one as we saw over here.
So when index is one we see that we have a one.
So neighbors at one is equal to true when we have this array right.
So we have this okay.
And then we are going to check vertices at one.
So vertices at one will give us b.
And then we will check whether b is there in the visited object or not.
So if it is not there, then we know that we have to push it to the queue and we have to mark it as
visited.
So let's do that over here.
Queue dot push and we are going to push vertices.
At I, which in the example that we just now discussed is B, right.
And then we are going to mark it visit as true visited at vertices at I.
Will be marked as true because we have pushed it to the Q so what do we push to the Q?
We mark it as visited and that's it.
So we are done with our, um, solution.
Right.
So whatever is uh, where whenever there is a neighbor which is not visited, we push it to the queue
and then we again come to the while loop.
If there is something in the queue we take from its beginning, that is, we shift and then we push
it to the output and that's it.
So we get our output.
So now let's just run this, and then we will walk through the code and see what's happening over here.
So let me just run this now.
So we run it.
See.
Visited is not okay.
So there is a spelling mistake.
V I s t e d.
Right?
So let's just quickly check where we have made that mistake.
Uh, we have visited.
Visited.
All right.
So it should be visited.
So that's the spelling mistake.
All right.
So.
We have visited over here.
All right.
Now it should work.
So let's try.
Yes.
And we get our solution.
We have a, B, F, C, E and d.
Now let's quickly walk through the code and see what's happening over here.
For this.
First, let's try to construct or visualize.
Basically, we're just trying to visualize the graph from what we have over here.
For this.
Let me just take a pen.
All right.
So let's quickly visualize the graph.
So we have a b c d e and f as the vertices.
Now let's look at a.
So this is the array for a right which shows the connections or the neighbors for a.
So we have a over here and it has a connection with B.
This indicates B right.
So we have a b and then we have c d e and f.
So we have a and f.
So let me just write it over here.
Now let's check for b.
B is connected to a which we already have a b c.
So b is connected to C as well.
D, E, and f, so B is connected to F as well.
So let me just write that connection over here like this.
Now let's look at C.
So C is connected to B.
We have that connection c d.
This is d.
So c is connected to d and c is connected to e.
So let's write e over here.
Now let's look at D.
This is D.
So d is connected to a b c which is already there.
Then you have d e.
So d is connected to e as well.
So we have this connection.
Now what about this.
This is e.
So e is connected to a b c so e is connected to c.
We already have that and e is connected to d we have that and e is connected to f.
So we need to make this connection over here.
So let's just write it like this.
And finally we check that f f has a connection with A and b.
We already have that over here.
And c d and with e so we already have that.
So this is our graph.
So this is how we can visualize our graph.
Now let's look at um the function over here Trav BFS which we have written.
Let's see what happens over here while we execute it.
So let's just take this down.
A little bit.
Okay.
So let's take a little bit more.
All right, so now let me just clear this up.
Now let's get started.
So we are traversing this graph and we are passing.
Add to it.
So that's what we did.
So let me just also make probably make this a little bit smaller so we can see the screen better.
All right.
Okay.
So we have that.
So let's now continue.
So what happens.
We have passed this graph over here.
And we start at a.
Now we have an output array.
So let this be our output.
Which is at this point empty.
And then we have visited.
So let's just track visited over here.
And then we have a queue, right?
We have a queue.
Let me just write that over here.
We have a queue and we put the start into the queue.
So we have a over here.
Now we come over here we mark it as visited right.
We mark a as visited.
So let me just write a over here.
And then we say true.
That's how our object looks like.
And then we check whether there is something in the queue.
At this point we see that yes A is over there.
So we take it out.
So we shift it and then we put it to the output array.
So we have a over here.
Now what do we do.
We find the current index from uh vertex indices where the current is a.
So current has the value a.
Now in using the object where we stored the key value pair, where the key is the the node value.
And then we get the index right.
So from this we will get that current index at this point is equal to zero.
All right.
So now we are just going to find the neighbors from this adjacency matrix at index zero.
Right.
So that's what we're doing over here.
Graph at zero.
So that gives us this array over here 010001.
All right.
Now we are going to loop through this.
Now initially over here when I is equal to zero neighbors at zero is zero.
So it doesn't pass this condition right.
So we don't go inside.
So I becomes one at this point.
Yes.
This is equal to one.
Now we are going to check whether vertices at one vertices at one gives us b.
Right.
Because we have our vertices array.
So this is equal to b.
And we are going to check whether b is there.
In visited we see that it is not there.
And neighbors at one is also equal to one.
So yes, we come inside and we push it to the queue.
Right.
So we push B to the queue and we mark it as visited.
Right.
So we have B over here as well as visited.
And again it's B and then the value is true.
So I'm not just I'm just writing B over here at this point so that it's easy for us to track.
All right.
So after this again we come to the next uh value of I which is equal to two.
Right.
Again it's zero three, it's zero four, it's zero.
And then at I is equal to five.
Again we have neighbors at five is equal to one.
So this is true.
And over here when the index is five at uh vertices five we will get a b c that the array was a b c
d e right a b c d e f.
So we'll get f over here.
And we are checking whether f is there over here.
It's not there.
So we will put f also into the queue.
And then we will put f over here in the visited object.
That's what is happening over here.
Now we are coming out of the for loop.
Again.
We check whether something is there in the queue.
Yes it's there right.
So let me just check change the pen and we take from the beginning.
Right.
We are shifting and then we put it to the output array and we are going to check its neighbors.
So for that we come to this part over here.
Right.
So that's done over here we get the index which is one.
And then we we check graph at one which gives us this array over here.
Now we get the neighbors one which is a and c and f.
So that's a c and f right.
So among these a and f are already there in the visited array.
So just c is not there.
So what do we do.
We push C to the queue and we mark C as visited.
So that's it right now again the same thing is repeated.
We come back to this place.
We see things are there in the queue.
We take out from the beginning.
We put it over here.
So we have f over here.
Now we have F, we get the index as five and then we come over here we get these are the neighbors of
F, so we have a B and E right A, b and e.
So we see that a and B are already there in the queue or are already there visited.
So we just add e to the queue.
Right.
And we mark E as visited.
We add it to the visited object and then the same thing is repeated.
We take out from the queue which is C.
Now we check the neighbors of C, right.
So over here we can see it has b and then d and e right.
So among these b and d are already there over here.
So we just add d to the visited uh object and we push it to the queue.
Again the we come to the while loop.
We see there are things in the queue.
We take out E, we put it to the output array, and then we check the neighbors of E which is over here.
Right.
So we see that it has c, D and f and c, d and f are already there in the visited object.
So we don't push anything to the queue.
And again we come to this check over here we see that yes queue dot length is one at this point which
is greater than zero.
So we come inside the while loop and we take D out.
We put it to the output array.
And again we are checking the neighbors of D from here right A, B, C and d we get 001010, which is
indicating that its neighbors are C and E, right C and E, so C and E are already there over here.
So we don't put anything to the queue and we are done.
We come out of the while loop because at this point the length of the queue is zero.
And this is our output.
Now let's check the output which we got over here.
You can see it's the same thing, right?
A, B, F, C, E and d.
So that is the output over here.
So that is how our function works.
Let's now quickly check the time and space complexity of this solution.
So the time complexity for breadth first search when it is when the graph is implemented as an adjacency
matrix, is of the order of O of V square, it's of the order of v square, and the space complexity
is of the order of v.
Now let's quickly understand this.
Now especially, let's see why the time complexity of is of the order of V square.
Over here we have this while loop, and this while loop over here will execute v times right.
So this will do v number of operations.
Now why is that.
So this will do operations as long as something is there in the queue.
Right.
And we are taking elements from the queue and putting it to the output array.
So that's what we are doing over here.
So every vertex will at some point come into the queue.
Right.
So I'm saying at some point not at once but at some point definitely it will come into the queue.
So that's why we can say that this while loop over here will do V operations.
So we have V operations over here.
And then we have this for loop over here.
Right.
How many times will this for loop operate.
Now.
Because our graph is represented or stored as an adjacency matrix.
Over here you can see that irrespective of whether a vertex has neighbours or not, for each neighbour
this will run.
This will do V operations right.
For example, let's take f.
This is f right.
This is f in our adjacency matrix.
So you can see f has only three neighbours A, b and e.
But even then the size of this array over here is still six which is equal to v right.
So this for loop will operate v times irrespective of whether a vertex has neighbours or not.
So for each of these v operations that is for each of these let me just write that for each of these
V operations we will do again V operations over here because we are storing the graph as a adjacency
matrix.
So that is why the time complexity is O of v into v or o of v square.
Now what about the space complexity?
The space complexity is O of V because of multiple reasons.
First of all, we are creating this output array which will have v elements, right?
So v is the number of nodes or vertices.
So that is one reason.
Now even if we did not have the output array, we still have this visited object which will have v number
of elements.
Right.
Because there are v nodes.
So this also will take v space.
And then we have the queue right.
The queue.
Also in the worst case like for example if the graph is something like this you have a then b, c,
d, e and f in this manner.
Then at one point.
So at one point let me write that at one point, or at the same time, there can be of the order of
v elements in the queue.
Right.
So that's the worst case in terms of space utilization.
So that's why we have that.
The space complexity of this solution is O of V.
Now let's quickly compare this and contrast this with the adjacency list implementation of the graph.
So in this case the time complexity we have seen is O of v plus e.
And the space complexity is O of V.
Now y is the time complexity over here O of v plus e.
That's because again over here we have a while loop.
So that will do V operations.
Right.
But inside the while loop we have a for loop.
But over here it will not do V operations for every neighbor.
It will for every node.
It will depend on the number of neighbors it has right.
For example, if you have a you have a then let me just write that over here B, c, D, e and f.
So we have the nodes over here.
Now we have a over here.
So A has only two neighbors right.
So over here this for loop.
When the current node is a it will I it will iterate two times.
Now for B it will do 123.
It will do it three times.
For C it will do one two, three.
So that's three times for C.
For D it will do one, two two times.
Right.
For E it will do one, two, three, three times.
And for F it will do three iterations one, two, three because it has three neighbors.
Now if we sum this up we'll get two plus three, five and then three plus three plus two.
This is ten plus three plus three.
This the sum over here is 16.
And you will see that when we drew this right.
When we visualize this this has eight edges.
So this 16 over here is nothing but two into the number of edges.
And that's happening.
So because this is a undirected graph.
So if there is a edge between A and B that will be counted over here as well as over here.
So that's why if we sum this up we will get two into E which is equal to 16.
So that is why we say that the time complexity is this v plus this two into e.
And this is just a constant.
So we can just avoid this.
So that's why over here we get the time complexity as O of v plus e.