In this lecture we'll learn how we can search a graph for a path, from one node to another. We can't just use the graph find method because that method simply returns a node with the value that we provide. And we don't want a reference to our target node. We actually want a path from our starting node to that node. This is obviously a really useful thing to be able to do if you have AI that needs to do pathfinding in your game. First, we'll look at how the searching is implemented. And then we'll actually see how it works for both depth-first search and breadth-first search. So our main method builds a graph and then does a number of searches. Think of these as test cases, if you'd like. And here's building the graph. So we have a number of nodes and a number of edges. And this is just like the picture I showed before we started looking at the code. And here's the meat of the work here, is searching the graph. And we provide the value at the start node and the value at the finish node. We provide the graph we want to search and we provide searchType. And searchType is just an enumeration that tells whether it's depth-first search or breadth-first search. We create a search list, which is a linked list of graph nodes. So this is the list of nodes that we need to search as we try to find a path from start to finish. We have a couple of special cases to look at. So if the start node is the same as the finish node we're already there. So we just return start.ToString because the path to the finish node is just stay where you are. If either the start node or the finish node isn't in the graph then there's no way for us to get from start to finish. So we return an empty string as the path from the start node to the finish node. And finally we get to the part that does an actual search. So the first thing we do is this is an int value, remember. Although, of course with a generic graph it could be any value but this example is with int. And so we find the start value in the graph and we put it into startNode. Then we create a dictionary that's keyed by GraphNodes. And the value is PathNodeInfo. So let's go briefly take a look at PathNodeInfo. This is a tiny class that just has a reference to the previous node. So we have a constructor that will create this PathNodeInfo. And we allow access to the single field in the class. So the big idea here is, when we're done, when we've found our way through the graph from the start node to the finish node, we needed to be able to say here's how I got there. And the way we'll do that is the end node will point to the node just before it in the path and then that node will point to the node just before it in the path and so on all way back to the start node. So basically, we can follow these references backwards from the end node to the start node. And once we have that information, we can just build the path in the correct order over here in the class that does the search. Now I certainly could add that previous reference to GraphNode. But that would kind of break the graph abstraction, wouldn't it? Because graphs aren't about paths between nodes necessarily. That's one of the things we can use graphs for. But it's not the only thing we can use graphs for. So we're attaching a little extra information. And we're not even doing it in a new class that contains both the graph node and a reference to the previous node. We're just storing it in a separate place and that separate place is this dictionary. And we'll actually find another great use for the dictionary a few lines of code down from here. So we add to the dictionary using startNode as the key. And startNode points to null because it's at the very beginning. So there's no previous node for the startNode in our path from start to finish. Finally, we add startNode to that list of nodes that we need to explore as we try to find the path from start to finish. Okay, now we go to while loop. And as long as there's a node to look at, then we will keep looping. We take the front of the searchList. So here's searchList, which is a LinkedList and we take First. So that's the front and we access the value. So that's the actual graphNode that the LinkedList holds. And we put it in currentNode. And then we take that node off the front of the list. We're about to explore it so we don't need to keep it in the list anymore. Now we're going to look at each neighbor of the currentNode that we're looking at. If that neighbor is the finish, then we found a path. And we'll add the neighbor to our pathNodes dictionary, Making sure that it points back to the currentNode so that we can retrieve the path. And then we call ConvertPathToString, which we'll look at when we're all done with the rest of the search. Here's that other great use of the dictionary. We can check to see if pathNodes contains the key for the neighbor. If it does, we've already taken a look at neighbor and that means we've just hit a cycle in our graph. And so we're just going to skip this neighbor. We're not going to do any additional processing for it. We're just going to jump over it and continue, which we haven't seen yet. Just says, go to the next iteration of the while loop. We don't want to break out of the while loop. We want to keep processing the search list. But we want to continue directly to the next iteration of the while loop. And so this is the way that we protect ourselves from getting caught in cycles in the graph. And dictionaries are super fast for finding out whether they contain a key. So that's a good way to check for cycles. Finally, this is a regular neighbor. So we're going to link the neighbor in the dictionary to the current node. And then we're going to add it to the search list. And it turns out that for DepthFirst search, we add to the front of the search list and for breadth-first search we add to the back of the search list. And it's the only thing we need to do differently between depth-first and breadth-first search through the graph looking for that path from start to finish. This is a debugging WriteLine so we can see what's happening. And if the while loop runs until there's no more search nodes and we haven't returned yet, then we didn't find a path. And so we return the empty string. Here's that ConvertPathToString method. So we're going to build a new LinkedList for the path. And we're going to add the endNode first at the front of that list. And then we will look at what node came before it. And while we haven't reached the end, so when we get to the start node, previous will be null. But before that we'll just be following our way backwards through the path. We add to the front again, this is how we're reversing the order. We add to the front again and we move along with the list. And then finally we just do a forward loop through the path to turn those GraphNodes into strings. So here's where we reverse the order of the backwards previous links into the forward path from start to finish. Okay, let's see how this actually works. And we'll start by looking at depth-first search. I'll run it to show you that this is real code that actually works. So there are all the test cases that execute. But we're actually going to look at some PowerPoint for depth-first and breadth-first search. Okay, in both cases we're looking for a path from node 4 to node 1. So when we start, we put the start node, the node 4, onto the search list. And that's the only thing on the search list at this point. Then we pull it off the search list and we look at each neighbor. And both 11 and 42 are neighbors, and they are not the finish node. And they are also not a cycle in the graph. So we put both of them on the front of the list. And it turns out that in this order, it's 11 and then 42. So now 42 is on the front of the list. And we pull it off the front of the list, and we look at both neighbors. And neither neighbor is the finish, and neither neighbor is a cycle. So we put them both onto the search list again. And then we do one more iteration. And we find that 5 has the neighbor 1, which is the finish, so we're all done. And our path is 4, 42, 5, and 1. Now that was actually just dumb luck that the order worked the way it did. Because we certainly could have wandered around the graph a little more. So the big idea is that we are going deeply into the graph as far as we can, looking for our finish. And if we don't find it then we're going to back up and look further and so on. So it's called depth-first search because we sort of go deep first. We pick a node to expand, and then we do all its children and then we pick a node to expand and do all its children. And that happens because we're putting the nodes onto the front of the search list. Breadth-first search works differently. So we start with 4 again and then we add both children. So this all looks the same so far. But remember we put those children on the back, not the front of the search list. So the next time through, we actually add all of the children of both those nodes. So essentially, what we're doing is, we're going one level into the graph, from the start node. Then we're going another level into the graph, from the start node. And then we go a third level into the graph. And that's where we find our finish node. So it turns out that, in the simple example we're getting both the same paths. But it turns out that breadth-first is guaranteed to find the shortest number of edges you cross to get to the finished node while depth-first may not. Certainly in a more complicated graph, you might find a longer path that leads from start to finish. Because you decided to pick the wrong edges to follow as you went deeply rather than broadly through the graph. To recap, in this lecture, we learned how we can use a LinkedList and a dictionary to find a path from one node to another in a graph. We also learned how avoid getting caught in a cycle in the graph. And finally, we learned the difference between depth first search and breadth first search.