Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms

all right so it is about 7:00 in the morning and today we are doing depth first and breadth first search the algorithms in general so we found a room first off I like to thank the Academy for this award I'd also like to thank my mom and my dad all right what's up so in this video we're going to talk about two fundamental search methodologies when you are searching not just not just graphs but relationships depth-first and breadth-first search are two fundamental ways to go about searching relationships it's not just about graphs we could be searching we would be searching graphs often but we could be searching distance between strains of like certain amount of changes between strings we could you be searching a tree so depth-first and breadth-first search are ways of searching they're not just about graphs they're a way of approaching things def for search and breadth-first search let's look at their differences so depth-first search uses a stack it either can be a stack that we create or it can be a stack that is the call stack where we use recursion this is why depth-first search can be done recursively on the other hand that first search is implemented iteratively with a queue a queue in first out of stack has last in first out so for a stack the last item to come in is the first one to come out for a queue the first item to have come in is going to be the first item to come out it's just like a line right when do we use depth-first search when do we use breadth-first search so we're going to use depth-first search when we do things like backtracking complete search exhausting search possibilities finding all the paths depth-first search is about going deep depth-first search goes deep it goes deep into a path explores all of it and then comes back outwards and then decides whether to go on to another path so Brad first search is great to check if there's a path between two nodes so say we start at F and we're looking for a so if depth-first search takes us all the way over here and then it goes all in there then it's just going to get lost in its exhaustion of possibilities instead of saying wait a is right there it was just it was just two steps out this case is not as extreme but death first search is going to get you to go too deep and then you'll get lost breadth-first is about going out layer by layer so this is what breadth-first search looks like if we started at C we're gonna explore here and then we're gonna explore one step out two steps out so breadth-first search is all about going wide slowly increasing the distance from our start node in giving us breadth instead of death also like I just showed you breadth first search is good for finding levels away from something this could be a tree this doesn't have to be a graph if we're trying to find how many level something is away like we want to do a level order traversal of a tree that's when breadth first search is our friend so like I said breadth-first search goes wide it does not go deep it's priority is to go out level by level breadth-first search priority is to go deep into its path come back go deep again come back and then go deep right so this is the difference within breadth first and depth first so now let's look at their implementation all right so this is the code for depth-first search for this function we are just passing in a node or start node and we're going to print every node in the graph using depth-first search so before we get into the code just to address the time and space so the time is going to be o V + e where V is the vertices and E is the edges we're traversing so you're going to see why that's V + e when we look at the code but we're going to be touching V vertices and then in each of the but we're going to be iterating over vertices edges which will add up to the E and then we're also going to have a space complexity of oh of V so the thing is for DFS with a stack if we're doing a tree and it's balanced we're only going to have all of H complexity because we're only caring about the items we have on the stack on Max and if our tree is balanced then we would only have max the height of the tree in the stack if it was unbalanced it be O of V or o then whatever you want to call the number of nodes so it really depends on what game structure working with but this is like a general general statement so here's the code for it so basically all that happens is you create a stack you need a stack for this because of the lastin first-out nature of the stack the lice last item we come in is the first to come out and then we need a scene hash set so we don't reprocess items and cause a cycle in our traversal so we need a hash set asset is just a set of unique items so we will only process nodes that we haven't seen first we add the first note to the start we begin our while loop and we continue while the stack is not empty while we have items to enter it over and process so we pull a note from our stack or queue in this case is def first search so it's a stack we pull an item from the stack if it has not been seen then we process that node how do we process the note we mark the note as seen and then we do whatever work we want to do with that node whether it's printing gate in this case we're just printing it but we get abstract a function out and do work with a function or something so it could be many things and then we need to continue the search we pulled a node we processed it and now we need to continue searching so then we go for each node that's adjacent to this node then we see if it has not been seen if the scene set does not contain it then at that node to our search and continue the search we're only going to do that the node has not been seen we're gonna process it has not been seen so it's basically those three steps pull a node process it add his children and the data structure enforces how we search if it's a stack it will be depth-first if it's a queue he'll be breadth-first so let's walk through an example here just to make things clear so we'll start at node a so let's add a D we add a to the stack we're gonna pop a from the staff and has a been seen no it has not been seen added to the seen print it out okay now we've pulled the node we've pulled the node we've added it we know it's not been seen we added to seen and we process that we printed it so now we need to add all of us children so we have BC de so now we can push these items because they're not it would they haven't been seen so so now we're back at the top of our while loop we pop thee has be been seen no be has not been seen we now need to do work on B we output it now we need to add all of these children so B let's go a has a been seen yes has been seen C no G no let's add them and yes these two are living on the stack at the same time we have to seize but we're never gonna process to seize because we're always checking if it's seen where they can live on the stack together but they're never gonna be processed twice and and you'll see how this pans out so now we visit see we're back at the top a wild look visit see have we seen seen don't we have not seen see and now what we have seen it but we haven't added it we had a process C so we process C so we added to our scene and we output C now we add all of these children so we have a B D we've seen it we've seen B we have not seen D a D and now we're back to the top of violin we had we process the mark D a scene we output D and then now we need to add all these children we pulled it process to add his children so now we need to go to D have we seen a yes have we seen C yes have we seen e no have we seen H no so now he needs add H and V so now we've had a chat and now we need to search so now we pull e we're back at the top of the wild so we pulled to eat have we seen a no we process that we output it outputting is the work we're doing it could be anything and now we need to continue so we need to add all these children so E has even seen yes has D been seen yes I've ever been seen no F is not been seen process we're back at the top of the while loop process that has that been seen no print it out and now we need at all s children has H been seen no has even seen yes has G been seen no so now we add H and G and then what we do now is we who are back to the top of the while loop and now we process G pop G G fringy and now we need to add all of Jesus ins has ever been seen yes has been yes so there's no more work to do with G and then we come to the back over the top of the while loop and now it needs a process H so now this is where we we go go through things so we process H we pull H I haven't seen it no prints it up earth added to the scene output it has F been seen yes has D been seen yes so now we come back to the top of the while loop and we pull H so we just pulled age and has H been seen yes H has already been seen in process so we don't process it and all of H and then we look at H's neighbors F and D I think T have been seen because this is no desire to be in process so nothing happens the no processing happens on this node it's been seen work has been done on it and we just popped it out so it's fine if two items are on the stack at the same time so now G now we have G on the stack let's pop G same thing that happens to gee-gees already been seen and if it's been seen that means we've processed it nothing happens none of his children get added if we look at g g f would be both of his children already process so we've already done what we could do with there's no so danny code it's been in the output so now we process the next node we're at the top of the while loop again we're at C so now same thing happens to see same thing happens to D and the same thing happens to E and now our stack is empty and the search is finished so all the changes between our bread first printing of notes and our depth first or from our depth first or breadth first all the changes is the data structure we use instead now we use a queue so now we're going to use a queue which has our our first in first out H or we're the first item that comes in is going to be the first that comes out just like a line and then we're gonna we're still gonna have the scene ash that we're gonna add the start node to our queue we're gonna go while the queue is not empty we're gonna pull we're gonna it's called pole for the Java API we're gonna pull the item from the queue if it's not been seen we process it and then for each adjacent then we're going to add it to the queue if it does not so it's basically the same thing it's just we change our data structure let's do it with let's do it on this graph so we start with a and we had we had a to the Q so we're going to pull a from the cube a has not been seen so we're gonna process hey it has not been seen we add it to this movie process a and now we need to add each of each of is kids so now we go b c d e so we're going to add them to the queue so we're going to add so now we add them to the queue so this is the front so this is the front this is the back so now we've added all the children and we're going to process B now we're gonna pull from the front of the queue so now we're going to process B and now we're going to add it to the scene and we're going to output B and now we add all these children that have not been seen so G has not been seen a has been seen C so we're going to add GMC to the back of the queue so we add those to the back of the queue and now we keep going we process C and now we add C we output C and now we need to take the children of C so a has been seen B has been seen and now we need to add D so we just add D to the back of the queue and now we're going to process the first node in the queue so now we take D and now we pull we pull D now we process it so now it will D and now we need to add all these children so de AMC so we we've seen a we've C and C and we need to add E so now we've added all these children so now we're going to add e or not we're going to pull the first item from the queue e he has not been seen we process it so now we need to add all of these children so a has been seen D has been seen has I've been seen no so now we're slowly getting near the end of our search has C if we pull the first node from the queue C has been processed nothing will happen we pull G from the queue G has not been processed so let's process it so now let's add all of G's children we've seen B we have not seen that when we have seen it but as a min process and now we need to pull the first item from the queue so we need to pull D has in process yes he has been seen in process nothing will happen so now he needs bull e has even seen in process it's been seen in process now he needs a pool F has been seen in processed No so now F is good process let's add all s children G and H so have we seen G yes have we seen H no so now we need to process we need to process ah so pull the first note from QF has F been seen and in process yes so now we need to pull H has H been seen in process - no so now our queue is empty and we have processed all of our nodes we have 8 nodes we've processed 8 nodes and as you can see one really key thing is the depth first search wasn't did it work work out as like well for you to like see this but breadth-first search works out very nicely you can see we go out level by level so let me write the level numbers so as you can see um for breadth-first search we go out level by level a is level zero B II D and C are in level one there are one level away so G F and H as you can see G F and H are two jumps away from a so we need to take two jumps no matter which way we go we need to do two jumps so this is what I was saying breadth first search is great for a level by level breadth-first goes wide before it goes deep death first search is all about paths and going deep into something so this is basically breadth-first search depth first search on the depth first search recursively is it's cleaner when you're doing things like like like the N Queens problem that I did it's easier to do the recursive depth first search but it's kind of harder to understand conceptually at least it was for me it takes time but I hope to do a video on the recursive as well but this is these are the basics of breadth first and depth first search breadth first goes wide depth first goes deep so yeah thing that's all [Music]

Channel: Back To Back SWE

Views: 136,809

Rating: 4.9246244 out of 5

Keywords: Back To Back SWE, Software Engineering, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies, depth first search, breadth first search, graph search

Id: TIbUeeksXcI

Length: 15min 22sec (922 seconds)

Published: Thu Dec 20 2018