In this lecture, we are going to begin discussing breadth for search.
So unlike depth for search, breadth first search is going to again start at a tree root.
So some arbitrary node.
And then instead of going all the way as deep as it can, it's going to fan out first.
So it's going to explore all the nodes at the present depth prior to moving on to the nodes at the next
depth level.
So that's the difference between depth first search and breadth first search depth first goes to tries
to go to the end, breadth first fans out and hits all the nodes at the current depth before continuing
on.
So to keep it congruent, let's go ahead and recreate our graph from the next or excuse me, from the
previous lecture.
So we add a CB.
We have DX with both of these funneling to it.
DX goes to E, which goes to F and this goes to G or to G back to EA.
We have
h, i, j k, and then we have an L here which connects back to EA as well.
So we are going to start at a and then our visited is going to be like this.
So we'll go from a, from a we can go to C at the same depth.
We also have B so we can go from A to B from C and B they both go to D so that's an obvious one.
D can only go to EA and now EA can go to F.
E can go to h h can go to I h can go to J and h can go to K.
So we got i j and k.
So also at E we have g.
And lastly, we have l.
So overall this concept shouldn't be too challenging since we have a really good idea of how depth first
search works.
Again, the key difference between depth first and breadth first is that depth goes all the way from
A to down here as quickly as possible without worrying about branching out.
So we went a D all the way to L before we even got to see in depth first.
Whereas breadth first, we look at everything that's on that depth level.
So we had a C, but we also had B, then we went to DH.
So that's the big difference between depth first and breadth first.
So what we can do is now we can go implement in our own solution to breadth first and run our test cases
on it to see how it will compare to depth first.
And we will begin implementing in breadth first in the next lecture.