OK, so let's get into coding this breath for research.
So pretty much have the same file that I use for death, for search.
I just kind of deleted the dev for a search function and the prototype, and I'm using that same project.
So if you want to do that and use the same project, that's totally fine.
Otherwise, if you want to start from scratch, for some reason, you can go ahead and do that too.
The only thing that I've seen so far is I included a deck, which is the double ending cue that you
might have noticed from the project.
You can use just a standard cue as well.
I don't know.
I use the deck, I just kind of put it in there, so that's what I'm going to use.
But to each his own, if you want, is a cue that's totally fine or whatever Dave structure makes sense
to you.
They can function like a queue.
Of course.
So then since I have that, I should go ahead and add it, so I'm going to add a deck of chairs and
I'm going to call that PFC queue.
Then I'm going to prototype a function just called BFS instead of DFS, which is going to be void.
And I'm going to have the starting Vertex attacks, which will be type char.
So it's just a prototype.
So let's do the actual one implementation.
So what do we have to do for this?
Well, let's think about it.
First off, we said that we had to push the starting Vertex two the queue.
So let's go ahead and do that.
So it'll just be your first queue dot, push back and push back.
Then we're going to start early of where we're going to loop as long as the queue is not empty.
So well, not the first queue empty and we will loop.
Then what we need to do now is let's see.
We need to get the first thing off the front of the queue, right?
So we're going to do childcare equals the VFX of the office.
Q Scott front and remember that we also need to pop.
So I'm going to also be your first Q Dot pop front.
So, yeah, now we're pushing back and popping for front.
And so what we do now is we're going to do a check to see if it's visited the country that we just made
the career.
And also we'll go, well, actually, we want we're curious if it's not visited.
So I'm going to say if not visited her, then we can go ahead and visit it.
So we will.
Let's see.
We also need to process it.
So we'll market is visited first.
So Phil visited her equals one to replace the zero with the one to make it true.
Then we'll just our processing is just printing it out.
Remember, that's all we're doing.
You can do whatever you want her processing it.
But right now, just for simplicity's sake, we are just printing it out.
So if it's not visited and we visited, Martha visited as true and we process it, and at this point
we are ready to look through its neighbors no makeup for a loop where we loop over the actual chars
and the string that is the value of the map.
So do auto and in four node in the adjacency list, which is still in our graph.
So the adjacency list care will give us that string of neighbors.
And then what I'm interested in now is if it's not visited, remember, we're going to put this if check
in here too.
So we don't have those redundant flashbacks to the queue.
So if I say if not visited in the node that we're currently on, then for that then we can push it back
to the queue.
So I'm just going to do only that one.
I think so.
I only need those brackets.
So we would do VSK Q Dot push back in.
Cool, so I honestly think that that is all we need, let's make sure.
Also, I hope this is big enough for you guys.
Zoom in just a little bit more.
Yeah.
So.
Typekit, let's see, we have here.
We pushed back the initial starting more attacks than we start our loop where we're going as long as
it's not empty.
We're getting the first thing from the queue.
So the first thing would be see, in the case of our example, that we had the theoretical example,
we get the first thing, pop it off.
Then we're checking, Hey, is this is this thing visited if it's not visited?
Let's go ahead and visit it.
Market is visited and then process it, then for all of its neighbors.
We are going to go through, and if one of the neighbors for each neighbor, the neighbors not visited,
then we're going to push that back to the queue.
And that is pretty much it, I think, to go down here, this is still left as depth first search.
So I'm going to change this to BFS and this is just us passing this starting node.
If you remember that and then all this stuff is already set up, I'm going to use the same file, which
is actually from the lecture that we did.
It is going to be the first graph that we went over that had more notes.
Remember when we did the slide with the Q, that was a slightly smaller graph.
So I'm using the the big graph that we walk through now and I can bring it up to check it once we run
this so we can make sure that it's correct.
So, yeah, I already have my edit configuration setup so you can go ahead and do that and then we're
going to run this and see if we got a correct output.
So let's take a look at this.
This is a city that is not correct, so we must have done something wrong.
So, Kurt, not me, that jumps out to me right away.
We want to seek out care and process care because that's what we're doing right here.
We don't want to be, you know, that's just the same starting vertex.
That's why I printed out all CS.
I'm pretty sure so.
Let's change that small mistake.
OK, see, ADF, FBG, JCI.
Let's go ahead and bring up this, so and this is our slide.
We have see a the.
If.
Be.
And then G6.
J.
H e.
I.
So PR. The same order.
And honestly, if you're using the same.
Text file, it might print out in a slightly different order, but it will still be and still should
be correct.
So remember we can have different orders.
The point is just to have the correct breath first search order where we're visiting all the neighbors
first, so you can still trace it through if it's different.
For example, maybe we didn't go to a first term.
See?
Maybe, you know, f- as a neighbor, maybe we went to F and then D and then a something like that.
And that would change the order, but it still is a valid breath for a search traversal.
So I just like modified my text, file my input file a little bit just to make it match what we were
doing here in the graphs so we could compare it.
Exactly.
But yeah, it looks like our breath research is in fact working, and it's all good to go.
So pretty simple.
You know, not very different.
We didn't change a whole lot from our death for a search, as you saw it's.
You know, pretty similar to the iterative death research I think of IDF research we did was actually
a recursive, whereas this is iterative and so you can do research recursively too.
But I mean, I could go over that.
It's easy if you want to look it up, it would be a quick change.
So, yeah, with that, hopefully this is clear enough for you.
Definitely good to try some different graphs.
That's a good way to practice, you know, make some different graphs with the different characters
and just.
Tweak it and trace it and.
Yeah, you know, really interesting algorithm, we will look at some more applications of this.
It's kind of similar to if you look back to binary searches, it would be similar to like traversing
level by level.
A level order traversal of a binary search tree is kind of related to breath research.
So we'll get into maybe a few applications and problems with breath research just so you can feel more
comfortable.
But hopefully this was enough to explain the general concept.
All right.
So with that, I'll see you in the next lecture.