[MUSIC] So to end here, I want to talk about the implementation of depth-first search. So, we've got a few questions here. First question is, how do we keep track of where to search next? Next question, how do we keep track of what's been visited? So we don't repeat and go in circles. And third question is, how do we keep track of the actual path? Since ultimately, we're trying to find a path from the start to the goal. So let's think about that first question first. How do we keep track of where to search next? How does the algorithm do that backtracking that we talked about? Turns out that this is really straightforward. We're gonna use an abstract data type called a stack. And the idea behind a stack is it's just like say a stack of books. And you can see a very precarious looking stack of books there. The idea is that in a stack, you're only allowed to put data in and take data out from one end. It's like a list but we've only got access to a top, just like in that stack of books. If I try to take a book out from the middle the whole thing's gonna collapse. So I'm only allowed to put data on at the top. And I'm only allowed to take data out at the top, which means that the very last thing I put in is going to be the first thing I took out. And that's gonna give us this depth-first behavior of the very last thing I was trying to explore from, well, that's what I'm gonna go back to, to try to explore further, if I reach a dead end. Next question is, how do we keep track of the nodes we've already seen? We need to do this in a an efficient way. Well, a good data structure for that is a HashSet. So a HashSet, built on some sort of a hash table, is a constant time collection of data where we can add, remove and find elements in constant time. And if you are with us in our last course, we talked a lot about hash tables and HashSets in that course. Finally, how do we keep track of the path from the start to the goal? Well, that's just a matter of keeping track of when you discover a new node, where did you come from? So you can kind of backtrack your way along the path that you took to get to that node. So in order to do that we'll keep a HashMap, which has a link from each newly discovered node back to the node from which it was discovered. So, putting all that together, we come to the algorithm for depth-first search, and here it is. So that first up there, we just initialize these three data structures that I talked about, the stack, the set of visited nodes and the parent map. Then we will start our search by pushing S onto the stack. So a push is just a way of adding an element to the top of the stack. And we'll also mark S as visited, by adding into that visited set. Then we're just gonna enter a loop that says as long as that stack isn't empty, as long as we've got somewhere else to go, let's start exploring. So we explore by popping the top node off of the stack. We'll call that curr. As long as curr isn't the goal, if we reached the goal then we should just stop. So, if we haven't reached the goal, then what we're going to do is we're gonna look at all of curr's neighbors. We're going to mark those all as having been visited now, cuz we don't need to go back to them. And then we'll put the neighbor into the parent map by putting curr as its parent. And then push that neighbor onto the stack, like stacking it up for exploration should we get stuck exploring. And that's all. Then we go back to the top of the loop and we've got a new current, which is one of the neighbors of the node that we were previously looking at. And that'll give us this depth first exploration of this graph. Now, before we end, I just wanna say one more thing, which is that this limitation of depth-first search uses an explicit data structure stack, an abstract data type stack in the code. We're explicitly pushing and popping from the stack. A lot of times, you're gonna see depth-first search implemented recursively. So here's the recursive implementation of that same algorithm. And what you can see in this implementation is, there's no stack. Where did our stack go? And it turns out that the way recursion works, is that there's a hidden stock down in your computer that is managing the recursion itself. So here's the recursive implementation depth-first search. Don't worry, if you don't know recursion and this doesn't make sense to you, don't worry about it. But you will see this implementation of depth-first search quite a bit because it's very simple, it's very clean and there's no need for us, the programmers, to maintain this stack variable because the computer will do that for us. So that's all for depth-first search. Up next, we're gonna talk about a very different kind of feeling search algorithm called breadth-first search.