Algorithms: Graph Search, DFS and BFS

Hi, I'm Gail Lock McDow, author of Kraken Coding Interview. Today I want to talk about graphs and common operations like breath first search and depth first search. So to go back to the beginning, a graph is basically a collection of nodes where each node might point to other nodes and these these edges can be directed. So like one-way streets or undirected so kind of like two-way streets. Now suppose you want to go walk through this graph and specifically suppose you want to do something like figure out is there a path from one node to another. There are two common ways of doing this and we'll talk about both of them. The first one is a little bit more simplistic and it's called depth first search and it's a typically recursive algorithm. And the way it looks like is saying okay we h have this initial node that I'm going to call S. Now you basically are asking a question hey S do you have a path to node T? And S says hm I'm not sure. Let me go ask my children. And first S goes to node A and it says, "Hey A, do you have a path to um node T? If you do, then hey, I'm done. I can give you my answer." Um, if you don't, then let me go ask B and then C and then D. And so, but the very first person we ask is A. So A gets asked, hey, A, do you have a path to T? I'm not sure. Let me go ask my children. And eventually we might get to get to a node who says why yes of course I have a path I am T. And so then we go and sayoop boop all the way back up. Yes there's a path. And that's the basics of depth depth first search. It's called depth first search because we go deep into some node before we even ask any of the children. Now the problem with this is that we might run really really far away. So imagine for example that B actually has a path directly to node T has an edge directly to node T. A might go to all of its children, all of its children, all of its children before even get to B and T was right there. There could have been a really fast connection. So that's why we might often prefer to use breath first search instead. Breath first search says, hey, go level by level out. So, first we ask S, hey, do you have a a path to T? And S will say, well, let me check if any of my nodes are T. No, there's no edge right there. So, each of those get in line. And then we ask the second level out and then the third level out and the next level and next level, next level. And so, we go level by level breadth. We go wider before we go deep. And that's why it's called breath for search. So I want to talk at a high level about the implementation of each before I dive into some of the details. So depth for search is implemented with a recursive algorithm. It's probably the simpler algorithm to implement. The only little trick is that you have to make sure to use an isvisited flag so that you don't wind up in some sort of infinite loop where there is you know a cycle and you keep asking each note if it has you start one around running around in a circle. With breath first search, the main trick you need to remember is you want to use a Q. So when you look when you look at S, you say, "Hey, do you have a path to T, you're going to go add all of its children to the Q and rather than going recursively, you pull out the first element to from the Q, check if it has a P, you check if it is this final element, and if not, go add all of its children to it. So you use a Q so that you go go through things in the correct order. So that's a high level how it works. Let's turn to the real details of the implementation. Now, I've gotten a bit of a head start on the implementation, but I'll show you just quickly what I've done. So, first we have this uh node class here, and it it's going to have some sort of ID that represents the node ID. Uh, and what I've done is give ourselves a mapping of from node ID to the actual node. And this is mostly going to be used for things like get node and add edge. This way we can actually just go and get um get immediate access to the node with particular ID. And then I've also given us this uh has path depth first search method and it's going to call out to this recursive method. So if you remember with with depth first search we need to have a way of flagging nodes to say hey I've already visited this don't retry it. So one thing we could do is we could actually modify the node class to give ourselves an isvisited flag, but that requires then making sure we clear the that flag later on. Another way of doing it is giving ourselves a hashet uh that lists all of the IDs that I've already of the nodes that I've already visited. It's sort of a replacement for a flag. So I'm going to do it this way. This way I don't have to modify and add a whole bunch of flags in and then make sure to clear them later on. So I get the source node. I get the destination node and then I get this create this visited hash set and then I go out and call the this recursive method. So now is where the fun begins. So first if I've already visited this node if visited.contains contains this source ID then return false because there is no path then uh okay otherwise then what I want to do is so now I want to go and make sure I you know update this mark this node as visited and then I want to say okay if if I'm at my source then return if I'm at my destination rather then return true because yes there certainly does a path then otherwise go and check all my children see if any of them have a path because if there's a path from a child to me then then there's certainly a uh final then there's certainly a path from me to my destination. So for each ch node to child in source adjacent if there's a path from child to destination passing in again visited then return true and that'll bubble all the way up the stack. If I get down to the very end and I haven't found a path yet then there is no path for me to my destination. Now let's turn to how breath first search works. Okay. So, breath first search. So, what I need with breath first search is I need a link list of sort of what I'll call the like next up. So, these are the I'll call this next to visit. These are the nodes that I need to visit next. And just as before, I need this visited hash set that represents everything I've already visited. And then I want to say next to visit first thing because the first thing I need to visit is in fact my source then as long as there is nothing in this. So while visited sorry now I'll next to visit is empty. So while it's not empty, keep going. All right. So first thing, so I need to look gra my very first node to visit. So node node equals next to visit dot I'll call this remove. So remove the very first node in that that list. If this is my destination then there is certainly a path. Now I also want to do my visited checking. So if visited.contains um of node ID then actually just continue. Let's go to the next value. Uh otherwise visited.add add of node ID. So mark it as visited and then go and actually add my children. So for each node child in node.adjacent go and add each of those to my next to visit. So next to visit add of child. All right. And that's all there is to depth. uh to breath first search and then of course if I get down to the very end and I haven't found a path yet return false. Let's walk through this code again and make sure that this makes sense. So hazpath dfs takes in the source and destination ids and then I get those nodes and then I create this hash set that should be a hash set not a hashmap and then goes and actually does this recursive method. So the recursive method take has this visited thing. So we use the visited hash set instead of marking the actual nodes with a flag. So visited check if it checks if it contains a source ID. Uh if it does contain that if I've already visited this return false uh because there's no path then otherwise go and add this visited mark this node as visited re you know check check my source as my destination shows I'm already there return true. um otherwise go and search all of my children then so that and then if I haven't found a path go return false. So with BFS we are taking in a source and a destination. So here I've used nodes I'll switch this actually to be symmetric and use ids again and so I'll make that public and this private now. Okay. So I take in the source and destination ids and then I go and call this recursive method. So my recursive method or sorry this other just helper method. So this takes in the source and destination. I create this list of the next nodes I have to visit and this visited hashet that should be hashet again. Uh and this marks all the nodes that have already visited. So I say okay next one to visit is my source. Then as long as there's there's something left to visit, pull out the next node to visit. Check if I'm where I should be. If so, return true. Otherwise, check and update my visited my sort of who's who I visited. And then go and ceue up my children at the very end of the queue to be visited next. And those will and this will this will ensure that my children are not visited immediately but are visited once sort of everything in you know everything scheduled has already been visited. So it ensure it'll visit level by level by level and then if I get found the very end and I haven't found a destination after all of this then just return false. So that's how breath first search operates. In many cases when we want to find if there's actually a path breath first search is often the better approach because otherwise we could wind up searching really really far away when there's actually a very short connection and it's certainly better when we want to find the shortest path. So now that you've seen breath first and depth first search why don't you try these out on a new problem. Good luck.