OK, so now that we have talked a decent amount about depth, first search, we are going to get into
the other algorithm that I believe I casually mentioned in the first death research lecture for a second,
which is breath for a search.
So let's get right into it.
So breath first search BFFs for short is different from death for search.
And in that instead of us like, let's say we start at some note here instead of us going deep.
First, we want to explore all the possible nodes that are nearby, neighboring adjacent nodes first.
And we kind of explore in layers like that.
So rather than us like taking a path all the way down, we are going to explore every adjacent node,
every neighboring node for a given node vertex.
So let's go ahead and just do a simple walk through it.
And I'm not going over the algorithm in detail right now.
I'm just showing what order the nodes would be vested in so you can pick any starting point.
But I think this is a similar graph to what we did in depth research, and I'm just going to start here,
probably how I did four death research, two, which is at this node.
See?
So let's go ahead and start there.
So we start to see I'm going to label the order so from see and I'm just going to choose to go.
I got to go to all of its neighbors.
So aid and efforts neighbors, right?
I'm just going to use a first.
So I go to a and then I'm going to choose the and then f.
So I visited all of its neighbors since he was number one, and we can go to number two now and I'm
going to explore that.
So its neighbors are B and C, but we've already explored C.
It's already visited.
So I am not going to consider that I'm just going to go here.
So that would be the fifth node.
And when something is already visited, that's an important thing to note, and I'm going to do a more
detailed walkthrough in the next slide, and I'm going to kind of be redundantly adding the visited
node so you can see, like how many things would actually be considered if we weren't kind of filtering
out the things we've already visited.
But in this example, we're not doing that.
We're just doing a simple walkthrough and ignoring what we visited.
So let's continue on.
So we explored a and this was its only new neighbor that we hadn't visited.
So now we're going to go from two to three, so let's look at Dee Dee.
We already have visited all of its neighbors.
So let's go ahead on to F if we haven't visited G so well, that's a G, then let's we were f.
That's for now.
We got to be.
So it's five.
What about these neighbors?
The ones we haven't seen are J H and E, so we do those three.
Between those three and we were at five for me now, we are six from Gee, we haven't seen, I see.
So we go to I at that.
And yet you notice that all of our nodes are visited now.
Of course, when we, you know, we went out and checked out, I mean, we would if we were six year,
we would want to go to seven.
You know, notice has no new neighbors, a notice that has no new neighbors.
I notice astounded neighbors and explore I.
But.
Everything is highlighted in our graph now, so are good to go.
So I made the graph a little smaller because it gets.
Really big with how many times we're checking out neighboring nodes.
If I don't do that, so now I'm going to go through this in more detail and talk more about the algorithm.
So if you think back to depth first search, you probably remember that we were using a stack to kind
of keep track of where we were and where we came from and all that.
And that's what gave us the death for search ordering really was being able to use that stat.
So that was a last in first out data structure.
And you remember the other one we talked about, which is the opposite, is a first in, first out data
structure, which is a queue.
So unlike death for search with the stack, we are going to be using a Q for breath for search.
So let's see how that would work.
I'm going to go ahead and start right here on the same node.
See, but it's a smaller graph and I have my Q kind of going here as I add and pop from it, and it
might need some additional space.
I can't remember if it overflows or not.
But let's get right into it and I will go over all the steps of the algorithm here.
So right off the bat, what we're going to do is push our starting node to the queue.
So we're going to do a push back on on the queue of our starting node.
And that is see then the next thing we want to do in this kind of is where our loop would start.
An iterative solution is we we would start a loop.
And the first thing we do inside that loop is get the first thing out of the queue.
So the front item.
So we get that out and that see and then after we get that from one out, then we would pop it off.
So imagine what just kind of popping it into a variable.
So we pop off.
See, and now that we have see, we're going to process and visit see.
And so I put this year and then we are going to check out its neighbors.
So what are these neighbors?
They're a D and F.
What are we going to do for those neighbors?
Well, we're going to add them all to the queue, so we add a d in to the queue.
After that, we just go back up to the top of the loop, so let's go back up and do the same thing.
So what is the first thing in the queue?
Because we thought that the first thing in the queue is a soda pop that out and get a.
Now this isn't a process, eh?
And then let's ask what are A's neighbors?
So A's neighbors are B and C.
And one thing that I'm doing is also checking, if you remember back to death for search, we had to
have that visited map where we would change anything that wasn't visited to a one when we visited it
and we checked to see if there's a zero or one there to know if it had been visited yet.
We're doing the same thing here.
So if a.
Was already like having this yellow ring that I wouldn't have visited it, so I'm going to ask that
each time actually before processing it, so we'll probably have a queue and then part of what we need
to do is ask, Hey, is this thing visited yet or not, if it's not visited and let's go visit it and
process it?
So that's another part to keep in mind.
So we're on a and A has C and B as neighbors, and normally what you would also want to do is check
the visited for the sorry check, whether the neighbors were visited already.
So you don't want to add the ones that are visited.
But just to show you kind of how much it adds up, I'm going to just add it to the queue anyways.
So it would still work out.
But it would be better not to add that stuff.
So I add CMB, although in our studio code, in the next slide, we will just be adding B because we're
going to make that check to see if it's visited.
So next thing, let's pull out of the queue and we're going to go visit because it's not visited, you
know, it doesn't have the yellow ring on it yet.
So let's go ahead and visit it and that having the yellow ring once again is kind of corresponding to
the map.
It has a zero or a one four visited or not.
Four.
So what are these neighbors?
Well, we have a CB and F. So I add all this.
Then I pull out if.
Visit F, because it's not visited yet.
What are its neighbors?
So those get at it, and I know I've mentioned it several times already, but we would not add the visited
nodes actually.
When we're implementing it, I'm just doing it here to show you how much the Q really builds up if you
do that.
So now we have see and we see out well, we've already visited everything for CES.
You can see that redundancy there.
So we don't do anything be haven't visited.
So let's face it being, we process B B has a and a d.
Sorry.
So we have A. J.
And now we're going to pop out, she's already been visited.
We're doing the same thing again, so you can see how this is becoming really redundant.
So be we've already visited that f we've already visited that.
She already visited that.
Of course, now we've had multiple season here, d already visited that.
Gee, we have not visited, so we will go ahead and visit and process G.
And F. Although, like I said, this is redundant.
A report about a and that's been visited, of course, has been visited, GE has, and so we will.
It's a J J Neighbours B redundantly push B and then F.
We have seen F and B out.
We've seen B.
You noticed there was a lot of redundancy here.
So that is why we are going to also make B check with the F inside of the lubed.
It looks for our neighbors as well.
So when we're adding neighbours to the queue, looping over all the neighbours of a given node, we
are going to only add it if it hasn't been visited.
So now this tells you that you are done, actually, because once the queue is empty, we are done,
we would go back up for a one one iteration.
And we would see that the queue is empty and the main outer loop of this would stop.
And that's when we know breadth first search has finished.
So let's take a look at the pseudocode.
So we start up here with the definition, we get these starting vortex parts to it.
And the first thing we did, just like when we push back, see and hear right away as we push back that
starting vertex, then we have this loop while the queue is not empty.
And while the queue is not empty, we're going to do all this in here.
The first thing we do is we grab the front thing from the queue and there's two things that should happen
here.
I didn't really put pop, but you should also be popping.
So remember when we grab the first thing from the front, we're also like popping it off so you can
think of it as like two steps or one step, but we need to reference the front.
And then after that, we would want to perform a pop on the queue to get rid of the front item.
Then we say if that thing that we just popped into this variable from the front, if it's not visited
Vertex, it's not visited.
Then let's go ahead and add it to visited, which is changing the zero to the one in the correct position
of the visited map.
Then we are going to process it, and this can be whatever, but we're just going to print it out for
simplicity.
At that point, we want to go through all of the neighbors of the current vertex where it so we go through
all of its neighbors and this is what I'm talking about to eliminate that redundancy.
We want to say if the neighbor is not visited, then we'll push it back to the queue.
Otherwise, we will not push it back to the queue.
And so that's pretty much it.
You know, just remember that I said we also hear it's not mentioned here, but I assume that you should
also pop off.
From the queue right here.
So you would get the thing from the front of the queue and pop it off the queue.
OK, so let's go ahead and recap as well on the time complexity.
So one thing now that we're kind of wrapping this up with the debt research and breath research, and
we'll go into the code of it in the next lecture.
Just briefly, but the time complexity is pretty much dependent for both of these algorithms, it's
dependent on the way that you implement the graph.
So remember, we had two things that we talked about in adjacency list or an adjacency matrix.
So really, what you want to be thinking about is the fact that the adjacency list is not really going
to yield the time complexity of Bigo of vertices plus edges and then the adjacency matrix.
Since we have a grid that is, you know, in vertices by and vertices that end by in dimension and you
have to go over all of the columns for all the rows that makes you have a time complexity of Bigo of
vertices squared.
So important things to think about when you are considering the time complexity of these algorithms.
So with that, I think that we're probably good to go and can head over to the code.
So I will see you in the next lecture where we will go over the implementation of the Code for Breath
Research.