[MUSIC] All right. So, to finish our exploration of basic graph search, we're going to look at another algorithm called Breath-first search. So, by the end of this video you'll be able to perform breath first search on a graph. You'll be able to implement the code for Breath-first Search, describe how the ADT (After Data Type) Queue works, and as well how Queues are used in Breath-first Search. So, we looked at this algorithm, depth-first search, last video, and we saw that it would explore all the way to the end of one path before going back and exploring down a different path. And the way we made that happen was to use a stack to store where we've been and where we want to go back to to explore next. So, that was how Depth- first Search works, with a stack just like this stack of books. But in this video let's consider the question. What if we change just that data structure that we use to figure out where we've been and where we want to go next? So, instead of using a stack I want you to consider, what if we use a data structure, an abstract data type called a queue. So, the way a queue works is, it's just like a line, say, at a movie theater. You get in the back of the line, and you come out of the front of the line. So, in a queue, you're always going to add elements to the back, and remove elements from the front. So we're working with two different sides of the list now. Where as in Stock we are only working with one side of the list and, those operations, just to get some terminology, are called enqueue, that's adding an element to the back, and dequeue, that's taking an element out of the front. We're gonna see that this very small change to this algorithm Is really going to fundamentally change the behavior of how it searches a graph. So, let's go ahead and make that change. So, here's our algorithm. It's exactly the same pseudocode as I showed you before, only everywhere I had stack I've now changed that to say queue. So, those parts in red. To say queue instead of stack or the appropriate queue operation, n queue instead of push, d queue instead of pop. And let's trace this code on the graph example to see how things are going to behave. So, just like before we initialize our visited set, we initialize our parent map which I'm not showing here and now we're gonna initialize a queue abstract data type so we put our start into the queue and we mark start as visited. What do we do next? Well, now we're gonna enter the loop and we're going to take s off of the queue and that becomes our current note. That becomes the note we're currently exploring from and we're going to explore its neighbors. We're going to go visit its neighbors. So, we visit the neighbors. We visit I and L. And in visiting them, we do two things, we add them to the queue and we put them in the visited set. So, we mark them as visited. All right. And then we want to explore some more. So, we look at the first node in the queue. The first node in the queue is I. So, we take I and we explore from I. At this point we again explore out from the neighbors. It's only neighbor right now is H, that already hasn't been explored. If a neighbor's already been explored or visited we won't put it back in the queue. So, we go to H. We add H to the queue. And we mark H now as visited. My question for you now, is looking at the state of the queue and where we are in our exploration, what node will be explored next? All right. If you said node to L, you'd be right. Remember, in our queue, we put H in the back, but the node we're going to take out next is the front. That node is L. So, Al is going to become our next current node. So, what you can see now, you can start to se, is that instead of going deep down one path, you're going broad out. So, we explored I, and now we're exploring L, and our search is going to color the graph in a very broad fashion, instead of a very deep fashion, like we saw with depth for search. So let's continue We'll just walk through the rest of this algorithm and you can see how it's gonna continue to explore outward in the graph. So, we explore L. L's neighbor is K. We mark K as visited. We put K at the back of the queue. Next, we take H off the front of the queue and explore from H. H's neighbor is D. We put D at the rear of the queue, mark D as visited. Then we take K off the front of the queue. We explore from K. K's neighbor is J. Put J at the back of the queue. Mark J as visited. We go back to D because that's now the front of the queue. So, we explore from D. We pick it's neighbor C, put it into the queue, mark it as visited. we now go to J and don't worry we're almost done. We now go to J. We take J as our current node, we explore from J. We put G into the queue, notice we haven't gotten to G yet, we know G's our gold node. But we haven't seen it really yet, we're just scheduling it to be explored by putting it on the back of the queue So, and we're marking it as visited because we know we're going to get there, but we don't go to G next. We go back up to C because that's at the front of the queue. So, we explore out from C. We take B, put in at the back of the queue, add it into our visited set. And only now do we get to go to G and find ha! Here we are at our goal. So, as you notice in this example, this did a very different exploration behavior than depth first search. And it was just that subtle change of what abstract data type we used to keep track of the notes that we needed to explore from. We're gonna end by talking about one example, one way in which depth-first search and breadth-first search produce actually different results on the graph. They both can be used to explore a graph, but some things, some properties of them are going to be a little bit different. So, one property is going to be that if we explore our graph. Let's go back to that original graph that we could reach our goal by going over the top. And if we look at the path that Depth-First Search found in this path, we can see that it's fairly long. It goes over the top but there was a shorter path that we could have found. And that's just because we got going on this original path that went up and we ended up finding the goal so we were good enough with that. But that path wasn't great. If you look at what breadth-first search does, in fact, it finds the goal from this much shorter path across the bottom so this is something that Leo is going to explore in much more detail next week when we start to really dig in to these graph algorithms. But for now, we're gonna switch gears and start talking about how to actually design Java classes for this graph problem.
