In this lecture, we are going to implement the algorithm breadth first search.
Now, this implementation is going to be pretty similar to depth for search.
But instead of our algorithm going all the way to the end of the graph, we want to fan out and hit
all our neighbors at that current depth.
So let's see what this would look like so we can say pub f in breath.
First search we want to pass in our graph.
We want our root vertex and we want our target vertex.
And just like in depth first search, we want to pass back or return an option with a vector containing
u.
X.
We want our visited which is going to be a hash.
Set vertex is and we want to create a new one
and we want our history.
And lastly, we need our Q which is going to be a vec dx Q and we need to make our cube mutable.
All right.
So we want to say we've already visited our root node since that is where we are starting out at and
we want to push back our root node and then we can have our Y loop.
So we have our current vertex again and we are going to pop the front of our queue.
All right.
So now we have our history dot push, our current vertex dot value, which we did in depth first.
And then if we reach the current goal, we want to return our travel history.
So if current vertex is equal to our target, return some history.
Otherwise we need to check the neighboring nodes for any that we have not visited yet.
So we can say for neighbor and current vertex neighbors of graph.
If visited does not can obtain our neighbor.
Then visited dot insert
neighbor.
And cue dot.
Push back our neighbor.
That way we're getting all of our neighbors at that current depth.
And then otherwise, if we're we don't ever find our target and all nodes we're already visited, then
we can return none because it is not inside of our graph.
So again, looks very similar to depth first search, but instead of us iterating all the way to the
end, we just look at all the immediate neighbors, visit those, see if it's the value that we're looking
for.
If not, then we can go up one more depth so we can now add in some of our test cases.
And let's.
Keep our test cases the same.
So we'll say test F in and we'll call it breadth First search and we'll call it fail.
And what we can do is actually come up here and we can create.
The same test cases that we were already doing.
So we're looking for a value here that does not exist.
So now we can say assert equals and we can say breadth.
First search, pass in our graph, pass in our route into and pass in our target dot or not target in
this case objective dot into and we want to see that it returns back none.
And then our other test case, we want it to actually find something.
So we will say, take all of this, copy it down and say F and BFS
found copy all this in, we will change our objective to seven.
And in this instance, we will say breadth first search and we can say path here.
And we can say let path equals a VEC.
And we expect our path to be one, two, three, four, five, six and seven because we expect 1 to
1, it's going to connect to two and three.
So we expect 1 to 3 to be visited and then we see two connects to four and five.
So then we expect four and five to be visited and then three connects to six and seven.
So then we expect six and seven to be visited.
So we have one, two, three, four, five, six and seven.
So let's run cargo tests to see how it looks.
And it says we expected an e num option, found our VEC.
We need to put some around our path
and the dreaded forgot semicolon.
There we go.
And we see that breadth first search fail and found both ran successfully so.
Safe to say that our breadth first search algorithm is also successfully implemented in and again,
you might have noticed that.
Breadth of research in depth research are extremely similar, and that is because they are.
So again, the big key takeaway here is that depth first is going to go to the end of the graph and
then it will work its way back to visit any any nodes that it may have missed, whereas breadth first
is going to fan out, meaning it'll get every single vertex at that current depth level before moving
on.
So if you have any questions about depth first search or breadth first search, please feel free to
ask them in the Q&A section and we will look over one more graphing.
Algorithm known as Dijkstra's Shortest Path.
And we will begin talking about that in the next lecture.