Hi everyone.
In this question, let's try to learn how to implement a breadth first search or breadth first traversal
in a graph.
Let's read the question.
You are given an undirected graph stored as an adjacency list in the first case, and as an adjacency
matrix in the second case.
Write functions to traverse this graph using the breadth first search approach.
As you traverse the graph, store the values of the vertices in an array and return this array.
So over here we are implementing the BFS or breadth first traversal approach for a graph.
Now there are two cases we have seen in the previous videos that we can store a graph either as an adjacency
list or as an adjacency matrix.
Now we are going to do both the cases over here.
We are going to implement BFS first when the graph is stored as an adjacency list.
And second we are going to implement BFS when the graph is stored as an adjacency matrix.
Now we have already seen BFS in the case of a binary tree.
Now the logic or the algorithm is going to be pretty similar to what we have seen over there.
Let's get started.
Let's say this is the graph which is given to us.
Now if we represent this graph as or store this graph as an adjacency list, it would look like this.
Right?
We have already seen how to do that.
So we have these six nodes A, B, C, D, e and f.
And we are just storing the neighbors of that particular node as an array over here.
So the neighbors for node A or b and f.
That's why we have b and F over here.
And because we are dealing with an undirected graph you can see that you have this link a to b in B
also.
Right.
So over here you have A as a neighbor of B as well.
That's because we have we are dealing over here with an undirected graph.
Now if it was a directed graph we have seen before, in that case we would not have this type of link,
right?
For example, if the link was from A to B, then we only have B over here.
We wouldn't have A over here.
All right.
So let's proceed.
So we have this graph and this is the adjacency list which stores this graph.
Now first let's try to understand BFS again.
For this I am just modifying this link.
I'm removing this link over here so that we can understand the meaning of BFS better.
All right.
So this is the graph which we have now when it comes to breadth first search or breadth first traversal.
The idea is that we have to visit neighbors of a node before we visit children of a node.
So let's say we start at node A.
And this is a difference between the case of a binary tree.
There we already have a root and we just start from the root.
But over here in the case of a graph, we have to mention from where we want to start the traversal.
Now let's say we are starting from this node over here.
So we are starting from a.
Now again let's read this.
We have to visit the neighbors first before the children.
All right.
So over here A does not have any neighbors.
So let's go ahead and look at its children.
We have B and F.
All right.
So again we also in this question we want to print the uh values of the graph.
Right.
So we have visited a.
So let's just store it somewhere else so we can see the way we are traversing the graph.
Also this will be helpful in that respect.
So after we have visited a we go to the next level.
So you can see that the the children of A or B and F.
So we will visit these two nodes after we visit A.
So we have b and f.
Now again how does this apply to visiting neighbors before visiting children.
Now after we have visited B, we could have gone to C, right?
Which is a child of B, but before we visit this child, we have to visit neighbors.
And that's why after B we have F over here.
Now once B and F are done, now we go to the children.
So B has a child C so we visit child C and there is no other child right.
So that is why after that we go to the child of F which is E.
Now if.
Be had a child.
So in this case be does not have another child other than C.
So that's why after C we go to E which is the child of F, but let's say there was one more child over
here C two.
Then after this we would have visited C two or it could the the order can change but we're just seeing
the levels right.
So we have we would have visited the neighbors before we visit child.
So we are not going to D which is the child of C.
All right.
So over here we are visiting C, then we visit E.
And after this we go to the next level which is D.
So you can see that this is one level B and f c and d is the next level.
And then we go to D.
Now this is very much different from depth first search.
In that case we would have gone as deep first as possible.
That is we visit children first before neighbors.
But in the case of breadth first search or breadth first traversal, we visit neighbors before we visit
child nodes.
So this is the idea of BFS.
Now let's go ahead and think about the algorithm which we can use to implement BFS in a graph.
Now we have this graph and it is stored as an adjacency list.
And we have the adjacency list over here.
Now the algorithm for BFS over here is going to be very much similar to the algorithm which we saw before
in the case of a binary tree for BFS.
So again we are going to use a queue.
So let's write that.
So initially the queue is empty.
And we also need an output array because as per the question, we are going to return an output array
with the nodes right with the value of the nodes.
So as we visit nodes, we're just going to push values to the output array.
And then to know that we have visited something, visited a node or not, we will need a visited object
so that we don't get into a loop.
And we never come out of it.
Right.
So we don't want to visit something again and again.
We only want to visit a node one time.
All right.
Now let's say we want to start at a.
Now this has to be specified for the BFS algorithm because unlike a tree there is no root over here.
So let's say we want to start at a.
So we have visited a.
So we push that to our queue.
All right.
So we push it to our queue and we mark it as visited.
So over here we say a is visited.
So we say a true.
All right.
So we make this entry this key value pair in our visited object.
Now let's have the pseudo code over here.
It's going to be very much similar to what you've seen in the case of the binary tree.
We are going to have a while loop, and the steps inside the while loop are going to repeat as long
as there is something in the queue.
So while queue dot length is greater than zero, we are going to repeat these steps.
So at this point we have a in our queue.
So yes this is true right?
Q dot length is one which is greater than zero.
So we come inside.
Now we are going to dequeue from the queue.
So we take the first element out which is a at this point.
And we are going to push it to the output array.
So we push it over here and we have a coming to the output array.
Now we are going to enqueue all the unvisited neighbours of this particular node.
So enqueue unvisited neighbors.
So that is the next step.
So in this case for this we will use our adjacency list and the neighbors of A or b and f.
And we will take b right.
Which is the first element over here.
We will check whether it is in the visited object.
No it's not there.
So we make an entry and we add it to the queue.
Right.
So we enqueue it and then we mark it as visited.
So whatever gets into our queue will be marked as visited.
So let's add it to our queue.
And we mark B as visited.
And then we take the next neighbor of A which is F right.
So f is also not there in our visited object.
So we make an entry.
So we have f and we say f is true.
All right.
So there is no other neighbor.
So we are done with this step.
And again we come to this check and we see that there are two elements in the queue.
Right.
So q dot length is greater than zero.
So we proceed.
We again d queue which is b at this point.
Right.
And we push it to our output array.
So you can see after A we have taken B and then we are going to enqueue the neighbors the unvisited
neighbors of B.
So at this point again we check our adjacency list.
We can see that the neighbors of b, r, a, f and c.
So we take the first element a, but it's already visited.
So we skip.
We move ahead and then we take the next neighbor which is f.
F is also already visited.
So we proceed further and we have c over here right.
And C is not visited.
So we push that to our queue and we mark it as visited.
So we push C to our queue and we mark C as visited.
And then we proceed again.
Queue dot length at this point is equal to two right.
So again we dequeue and push f to our output array.
And then we are going to enqueue the unvisited neighbors of f.
At this point the neighbors of f are a, b and e and a and B are already there right within the visited
object or the hash table, so only E remains.
So we push e to the queue and we mark e as visited.
Now over here remember we are doing BFS or breadth first search.
And we want neighbors before children.
So to ensure that you can see over here what's happening is in the queue.
We are pushing neighbors before children.
So over here when we were at A we pushed B and F together right one after the other.
And later when we get to B only at that point we are pushing C, which is a child of B, right.
So this is the way that we are ensuring that.
And then we are removing from the beginning.
Right?
We are dequeuing that is, we are taking from the beginning.
So it's a Fifo data structure.
The queue first in first out.
So in this way we ensure that we get neighbors before children.
All right.
Now let's again proceed.
So we have uh we have F in our output array.
Now we added e right.
We added e.
Now this is over again.
There is something in the queue.
So we dequeue right.
So we dequeue.
So we take out C and we add add it to the output array.
And then we check the neighbors of c, b, e and d.
These are the neighbors of C.
Now among this b and e are already there in our hash table.
So only d remains.
So let's add it to the visited object or the hash table and we enqueue it.
So we have D over here.
All right.
Again, the queue is still not empty.
So we de queue and we push E to our output array.
And we are going to check the neighbors of E, which is D, C, and F.
Now D, C and F are already visited, so we don't enqueue anything.
But again, when we come over here we see that the queue is not empty.
There is still one element.
So we'd queue and push it to our output array.
And then we are going to check the neighbors of D, which is C and E, and you can see that C and D
are already there in our visited hash table or object.
So we don't enqueue anything.
And again when we come again and check over here, we see that the queue is empty or the length is zero
and zero is not greater than zero.
So we are done.
And this is our breadth first search or breadth first traversal.
So we go from A.
Then we have b and f which are in the same level.
Then we have C and E which are in the same level.
And then we go to D which is the last level.
So in the breadth first search we have seen that we take neighbors before children and we use a queue
to implement the BFS.
And again notice this is very much similar to the implementation of BFS in the case of a binary tree.
And we have done that question in the case of a binary search tree.
Right.
So the same applies in the case of a binary tree as well.
All right.
Now let's proceed and look at the space and time complexity of this solution.
Now first, let's look at the time complexity.
The time complexity of this solution is of the order of V plus E, where v is the number of vertices.
In this case we have six vertices and e is the number of edges.
Right over here.
What's the number of edges?
Let's just check this is one.
This is two.
This is three.
This is four, five, six, seven and eight.
So we have eight edges.
So the time complexity is of the order of V plus e.
Now let's try to understand why that is over here.
This algorithm is to traverse the graph.
So traverse means we are going to visit every node once right.
So because we visit every node once we definitely do V operations.
So that is why we have v over here.
Now when we look at the algorithm this is done by this part over here right while q dot length greater
than zero.
So at if you take all the instances together you can see that we will get all the nodes at least once
and exactly once.
Right.
All the nodes will be there.
Exactly once in our queue.
So you can see that over here.
Right.
So this while loop over here will happen v number of times because we will have v elements in the queue.
Right.
So this is what takes care of this v over here.
Again remember we are traversing every vertex.
So we have to do v operations.
So that is why we have our v over here.
Now what about this e over here.
This is for because of the for loop which is which will be used to enqueue all the unvisited neighbours.
Right.
So that is why we have e over here.
Now how does this turn out to be E.
So let's take a look at the algorithm.
So we have this pseudocode over here.
So this part of the code takes care of enqueuing unvisited neighbors.
Now when we are at a right.
So this part over here will loop two times.
Right.
Because there are two neighbors for a.
Similarly, when we are at node B this part will loop three times because there are three neighbors
of B.
So let me just write that over here.
So this this does it three times when we are at node C, this part over here will loop three times because
there are three neighbors for C.
So again that's three.
When we are at node D it has two neighbors.
So over here this will check it two times right.
The for loop will be going for two iterations.
And when we are at E again it will be three times.
And when we are at F the for loop will happen.
Three will do three iterations, right.
So the total number of operations which is happening over here is two plus three plus three plus two
plus three plus three.
So two and three is five three and two is five.
So five and five is ten and ten and six.
That's 16 operations.
And we have seen that in this graph over here we have eight edges.
So 12345678.
So we have eight edges.
Now therefore this over here this is actually two times this is actually two times the number of edges
operations.
Right.
So we can say that the time complexity is actually O of V plus two e.
But because two is a constant we just avoid it.
And that's how we get e over here.
So the time complexity is O of v plus e.
And again we have a two over here.
Because the graph which we dealt with over here is an undirected graph.
If it was a directed graph then if it is stored as an adjacency list.
So the total of all these would be equal to the number of edges.
So in that case also the time complexity is O of v plus e if we implement BFS.
All right.
So we have understood why the time complexity is of the order of V plus e.
So we are doing operations of the order of V plus e.
So this v is accounted by this while loop over here.
And then this E is the total of the of the operations that will be performed by the for loop over here.
And we have seen how we get to E in this case.
Right.
Because at every node we will be doing a for loop to traverse the neighbors of that particular node.
All right.
Now we have understood the time complexity.
Let me just clear this up.
Now let's take a look at the space complexity of this solution.
For this, let's try to think what takes up auxiliary space.
Right.
Again remember this adjacency list over here is given as part of the question.
So we are we we are only dealing with auxiliary space.
So when it comes to space complexity it is equal to of of the order of V.
Because only this visited object takes extra space.
Right.
And again we have this output array.
Now if we did not want an output array then also space would be taken up by the visited object and then
also by the queue.
So let's just write that out.
So what are the elements that take up auxiliary space or extra space.
We have the visited object over here.
We have our output array and we have the queue over here.
All right.
Now the visited object clearly will take v number of key value entries.
Right.
Because for every node we will have one entry.
So that's why this is going to take space of the order of V.
All right.
So this takes space of the order of V.
Again the output array is also going to have every vertex right.
So.
Again.
This also takes up O of V space and the queue.
The queue we have seen in this case takes up less than O of V space.
But if we take the worst case possibility of the graph, let's take a graph that looks something like
this.
Right.
So we have node A and this node over here is connected to every other node.
So when we enqueue the neighbors of node A we will have b, c, d, e and f at the same time in our
queue.
Right.
And that is equal to v minus one elements.
So we can say that in the worst case the queue also will take o of v -1 or 1 is just a constant.
So we avoid that.
And in the worst case the queue itself can take O of v space.
So each of these take up O of v space.
And hence we say that the space complexity of this solution is O of v.
Again, remember we could say o of a constant into v, but then we remove a, we remove constants and
therefore the space complexity of the solution is O of v.
In the next video we will see how we implement BFS when the graph is stored as an adjacency matrix.
And there you will see that this time complexity changes.
Let's see that in the next video.