Graph Algorithms for Technical Interviews - Full Course

Key Takeaways

this course will help you learn what you need to implement graph algorithms and use them to solve coding challenges alvin's dynamic programming course is one of the most popular courses on our channel and now he's back to teach you graph algorithms hey programmers i'm alvin from instructi welcome to our course on graphs in particular this is going to be about graphs for your technical interviews of course graphs are a very common topic when it comes to those technical interviews in particular what i want to emphasize throughout this course is the handful of patterns that come up time and time again on those technical interviews in just about two and a half hours i'm gonna give you all the tools you need to basically cover i'd say about eighty percent of all graph problems and so what do i have in store for this course well i think the key to victory for your data structures and algorithms and especially your graphs is to visualize things right so we're going to do is trace through a lot of different algorithms and be sure to understand them at a high level and that means going through different animations here i think graphs have a pretty bad rep for being a difficult topic because to a beginner you can have very very different narratives around a problem and not really understand they're all really based on a graph premise so we're going to realize that a bunch of different things could be understood as graphs so when it comes to the prerequisites of this course i'm going to assume that you know nothing about graphs but you do know how to code right so i'm going to have the expectation that you understand some recursion so as you work through the course and learn about different graph patterns we're going to use those patterns to solve some very classic interview problems about graphs right i'm going to give you plenty of opportunity to practice these patterns and different problems that way you'll be ready whenever you have them on a technical interview what i love about the topic of graphs is just using a handful of different algorithms you can cover the majority of graph problems right for every graph problem that we cover we're going to split it up into two sections section one is going to be about the approach for the video so we're going to go over the strategy and overall theory and be sure to sketch out a nice meaningful picture we're also going to talk about the complexity of the algorithm in the approach video following every approach we're also going to implement the code of course i'm going to be writing all of my code in javascript you'll be able to follow along in any language that you like so that means occasionally i'll be switching to my code editor where you of course can follow along we're also going to be sure to provide links in description as well as links on screen that way you can formally read the prompts for every problem as well as look at the different test cases all right i think that's enough introduction for now let's hop right into the course all right programmers let's jump right into the course i want to start by giving you some background about your graphs we're going to go over the graph basics that you need to start attacking problems in a technical interview so first off what is a graph a graph is really just a collection of nodes and edges so with respect to nodes you can visualize them as typically just some circles with some data inside of them so i'll put some letter values in my nodes over here and when we refer to edges that would be just any connections between nodes so for example there was a connection between a and c it would look something like this right what i can formally say is there's an edge between a and c i can create many edges between any nodes i want within this graph another word you might hear out in the wild when it comes to describing nodes is you might hear the word vertex being used right they're really the same thing in this course i'll stick to the word node and an edge is just a connection between a pair of nodes that's really all a graph is at a high level where things get interesting is how we can use this graph framework to actually solve a problem right so if you think of these nodes as just things and the edges as relationships a graph is great at describing the relationship between things for example we can say that the nodes here are cities and edges would be roads connecting cities or in a similar way maybe our nodes here are courses and then the edges represent prerequisites and so in the future we're going to use graphs as a way to illustrate and frame some narrative problem let's talk about this graph in particular here i really have drawn a directed graph and that's because i have some arrowheads along the edges that would be in comparison to an undirected graph here i have really the same structure except i don't have any arrowheads on the edges here and that means that there is no directionality to it right if i look at the directed graph let's say i was at the node a well then i can travel to b or c let's say i move to c however once i'm at c i cannot travel to a i can only travel to e right that's because i have to obey the direction of the arrow heads here if i take a look at my undirected graph let's say i was currently situated at the c note over here then i do have the option of traveling to either a or e right so if i travel to a that's all good i can even travel back to c so think of a undirected graph as a two-way street for now we'll just continue on with our directed version let me also introduce some useful terminology we can use when talking about the nodes in our graph if i was currently situated at this a node i can refer to b and c as neighbor nodes right so a neighbor node is really any node that's accessible through an edge of course obeying the direction of the edge in other words if i was currently situated at the c node then i only have one neighbor of e right if i'm at the c note then i won't consider a a neighbor awesome when you visualize graph algorithms you should really sketch a picture that looks just like this right literally draw nodes of circles and arrows as your edges here however when it comes to how we implement this algorithm in some code we're going to have to represent it in a more programmatic way right so in my brain i think of this image of like nodes and arrows between them however in my program i'm going to use typically an adjacency list it's probably our preferred way to represent graph information right so depending on the programming language of choice you're going to use typically we would use some hashmap data structure to represent an adjacency list really you're looking forward to using some constant time a lookup data structure that has a key value pair mapping right so if you're in javascript that'll be an object if you're in python that'll be a dictionary if you're in a language like java or c you'll be using an unordered map looking at this hash map i've drawn or this adjacency list the keys of this adjacency list are going to be every node in my graph right so i just have all of the node values a through f laid out as the keys however if you look at the corresponding values the values are actually going to be an array right so if i look at this very first entry it says that i have a node of a and then in the array i've populated all of the neighbors of a that is a has two neighbors of b and c that's why i have this correspondence within my adjacency list that holds true for every entry within my adjacency list so for example let's say i look at the entry for e so i go to the spot in my jc list where the key is e it only has one outgoing edge to b that's why the array for e only has b inside of it one thing to also note is even if a node has no neighbors it should still appear as a key within my adjacency list for example if you look at the d node d has no outgoing edges that's why its neighbor array is empty however it should still at least appear as a key within my adjacency list right that way i can still know that the d node exists so at the start of the course we'll usually be taking in adjacency list as the information to represent a graph right but as we sketch through things on the whiteboard we should be visualizing them using a nice picture like this awesome so let's actually jump into our first pair of algorithms to me the must-know algorithm for a graph is really going to be to do some sort of traversal on it why don't we start by talking about a depth first traversal something you may have heard of before right now we're going to talk about the depth first reversal algorithm that operates on a graph so let's start by understanding at a high level what ordered a depth first reversal would give you so let's say i had some starting node and i'm going to choose a as my starting node right so i'm going to color it here in yellow if i was following a depth first reversal now that i've you know chosen as my starting point i can either hit b or c next i'm just going to commit to using b so let's say i had the sequence so far of a comma b and at this point if i was truly following a depth first traversal i must go deeper to the d node in other words i don't go to the c node yet cool that would be a true depth first reversal right and at this point now that i've bottomed out a d d is a dead end right i can't travel to f from d because that would be disobeying the arrow head and so now i can move to that other neighbor of c and from here the algorithm would continue right i go from c to e and then e to b and technically i would have to double traverse some nodes like b and d over here so overall in this yellow coloring i have colored the full region that a depth first reversal would explore starting at a notice that if you started at a it would be impossible to reach f and that's kind of normal right that's kind of why we use these traversal algorithms it can tell you whether or not you can travel between some nodes and we'll see that literal problem later on right so you're probably wondering you know exactly how do we implement this but for now i just want to stay focused on the order that we got right so just regarding our debt first reversal if we remember the first three you know iterations of the algorithm we hit the sequence of abd right that's indicative of a depth first reversal now let's compare that to the breath first variant so i'm going to lay down the same exact graph we're also going to start a traversal at the a node but this time follow a breath first order so i have a first and let's say you know i chose b as my next node when it comes to a breath first reversal it doesn't matter like which you know initial neighbor you choose so i'm just going to choose b but now that i've chosen b if i was following a true breadth first reversal i must hit c next right and that's the main difference between our depth first and breadth first reversals for the same graph my depth first would start abd whereas my breath first would start abc and so you're probably wondering is is there any importance between this nuance right when would i prefer depth first over breath first or vice versa either a depth first or a breath first traversal would explore the same exact nodes within a graph however it would explore them in a different order right and this is more obvious to see when we have a larger graph with way more edges and so let's look at how that first traversal explores again but this time on a much larger graph let's take a look at this one so i'm going to choose some random node as a starting point let's say i chose this node in yellow if i was doing a depth first traversal what i'm going to do is you know pick a direction and travel in that same direction as far as possible before switching directions so let's say i move to the right at this point i would have to continue moving toward the right until i can't move to the right any longer at which point i have to choose some new direction so let's say it was downward i would keep doing that until i can't move downward anymore and so i'd have to move to the left now and i would keep chasing this single path in a very deep direction and so that's behavior indicative of a depth first reversal right you're exploring one direction as far as possible before switching directions let's compare that to a breath first traversal so let's say i started at the same note in pink if i was following a breath first reversal it would look something like this from the starting point i would explore all of the immediate neighbors of this node kind of in a circle like this now i just keep applying that behavior so what you notice about the breath first reversal is it'll tend to explore you know all directions evenly right instead of just favoring one direction all the way through that's really the only difference between a depth first and a breath first reversal later on the course i'll bring up explicit problems where you might prefer one over the other all right but for now what i want to do is give you all the background you need so you can actually build this algorithm we'll kind of talk about things at a high level consider this the pseudo code then of course we'll express it in some javascript code later on so when it comes to actually implementing and code these two algorithms the key is to understand that a depth first traversal uses a stack and a breadth first traversal uses a cue recall that a stack is something where you add to the top and remove from the top as well whereas a cue is something where you add to the back and remove from the front and it gives you two very different orderings that's really the only difference between these two algorithms so let's start by tracing through our depth first traversal of course using a stack so i'm going to use a slightly different graph and to visualize my stack i'm going to use this bar to represent the bottom of my stack obviously for me at least i think of a stack as some vertical data structure cool so let's say i just arbitrarily chose a as my starting node to perform my depth first traversal right in the long run just want to print out all different node values within this graph so what i'm going to do is i'm going to take my starting node of a i'm just going to immediately initialize it onto my stack so right now a is the only thing on my stack it's also at the top of my stack and now i can enter the flow of the main algorithm here because i have a stack what i can only do is remove the top of my stack so that means i pop off a from the stack and consider the a node my current node being looked at right at this point let's say i print out a to my console and from here what i want to do is consider a's neighbors right so if i look at the c node what i should do is just push c to the stack then also push b to the stack right and it doesn't matter like in which order you push these neighbors if i wanted to hit b first then i'm going to push them second right awesome that would end like my first iteration of this depth first traversal cool so at this point i can look at my stack and my stack still has some data on it so what i should do is again pop the top of my stack so i'm going to pop b off my stack and that becomes my current i'm also going to print it out at this point i look at b's neighbors b has one neighbor of d and so i push d to the top of the stack notice that because i have a stack d ends up on top of the c right and so now when i get to another iteration when i pop the top of my stack i look at the d node as my current right and i can print out d and this feels good because so far my print order would be abd notice that i kind of pursued that single path deeply following abd but i have to look at these neighbors i can take f and just push f to the top of my stack next iteration my stack is still not empty so i should do is pop the top f is now my current i can print out f but f has no neighbors so f isn't going to push anything else to the top of the stack right at this point i get to this next pass and i pop the top of my stack and that means c is now my current i can print out c's value and then i can look at c's neighbors and i just push e to the top of my stack on this last iteration i pop the top of my stack e is now my current i print out e since e has no neighbors i don't push anything else to the top of my stack and at this point i've reached the state where my stack is empty and that means my algorithm is done right that means you explored as far as possible within your graph notice that it might not necessarily be the case that you're able to hit every node of the graph in this particular example it was possible though awesome so let's redo that trace using our breadth-first algorithm which means we just adjust things slightly and we use a queue order right remember that a queue is a first in first out data structure meaning things enter to the back and then they leave from the front and so let's say i use this arrow to represent the directionality of my queue right and i start the algorithm in the same way for my breadth first reversal let's say i want it to begin at node a so i just initialize my q with a cool so i start by removing the front of my queue so a becomes my current node i can print out a as well and now i consider a's neighbors right so i consider b and c if i wanted to travel to b before c then i should push b to my q first right so i add b to the back of my q right and i should also add c to the back of my queue right and that would actually end my first iteration so now i look at my queue it still has some stuff on it so i remove the front of my queue that means b becomes my current of course i print out b now i consider b's neighbors so i just look at the d node and i push d to the back of the queue since d enters through the back it ends up behind the c and that's really important behavior next iteration i remove the front of my queue so my current is now c right i can print out c and then look at c's neighbors of just e and i add e to the back of the q which means that in the order of my q e ends up behind d on my next iteration i remove d from the q and i print out d and add its neighbor of f to the back of my q next iteration i remove e from the front of my queue print it out since e has no neighbors e is not going to add anything else to the back of the queue and of course finally f leaves the front of my queue i print out f f has no neighbors at which point now my q is totally empty and since our q is empty that would be the end of our algorithm all right and that's all there is to our depth first and breadth first algorithms they're going to be the nice baseline code that we use to solve many different graph problems i think that's enough theory for now what i want to do is now switch to my code editor where we can actually implement these in javascript hey programmers so here i am in my editor what i want to do is now show you how to implement those depth first and breadth first algorithms so we'll start with the depth first and my goal is really just to build a function that will print out all of my values in the graph according to a depth first traversal right so i'm going to define this function depth first print make it an arrow function javascript it's going to take in the graph which is going to be given as a nice adjacency list and this is actually the same graph in that last example we traced out i'm also going to need to specify some starting node here i'll call it a source node i'm going to begin in the traversal starting at that node cool and so we know inherent to a depth first traversal is going to be a stack so i'll show you how to implement this iteratively which means you need an explicit stack for me in javascript that's as simple as just using a javascript array right i'll make it empty at the start and i can use this array as a stack if i just commit to using operations that manipulate the same end of the array in other words if i just use push and pop that will always manipulate the end of the array right removing and adding to the end of that array what i want to actually be sure to do is i want to initialize the stack with my starting node that is with my source node remember that like a node here is really just designated by some character cool and when it comes to designing like the main loop for the algorithm here you want to keep running the algorithm while the stack is not empty in other words while stack.length is bigger than zero that i have to keep running that's very reminiscent to what we expressed on the whiteboard so when it comes to performing like a single iteration of this depth first what i want to do is remove the top of my stack so if i do stack.pop that will remove the last item of an array in this case like the top of my stack and also return it to me so i'm going to save that to a variable i'll call it my current and so this point would actually be a great opportunity to just print out that current so all console.log current right so looking at you know this example over here since i initialized a stack to contain just the source node of a on the very first iteration this y loop i would of course pop out a then i would print it out all right and from that point what i want to do is consider a's neighbors of b and c so if i want to look at like the array associated with a i can just key into my graph right because my graph is an object right now so if i say graph square bracket current right if current is a that means graph square bracket current would give me back this array i want to iterate through every node or every neighbor in that array so i'm going to nest a loop here i'm going to say 4 let neighbor of that array so if you're unfamiliar in javascript if you just use a forward of loop that will iterate in order through an array so now i'm hitting neighbor as b and neighbor sc what i want to do with those neighbors is simply push them to the top of my stack so that will just be stack dot push and push this neighbor awesome i'm going to be sure to push every single neighbor that it has so sometimes i'll have two neighbors other times i'll have one neighbor or even no neighbors that's really all there is to implementing a nice baseline depth first print something that i do want to point out my favorite way to implement this algorithm is to consider like processing your node when it leaves the stack not when it enters the stack in other words i usually write like my print statement right after something is popped and the thing that i pop is exactly what i print right so let's go ahead and give this a run see what we get it looks like in my terminal i got the order of a c e b d f which you'll notice is slightly different from what i expected from over here however this would be also a valid depth-first traversal we have to bear in mind is you know depending on like the arbitrary order of values within the same neighbors array you could tend a different direction at first right the most important thing i look for when it comes to verifying a depth first is to make sure that i you know chase the same direction before switching directions right so since i started out with ac so i go a and then to a c over here the next move would be going to e and that's exactly what happened in my code right and then once i hit e e is actually a dead end so then i can go on to my other lateral neighbor like b right and so i can contrive the same order i expected here if i just flipped this right so i put c followed by b i'll give that a run they're both valid uh depth first traversals let's see what we got now cool now i get the exact order of abdfce and really think about why that is right so let's say that i just popped out a from my stack so i printed out a that's nothing fancy right and then from there i start iterating through the array that's associated with a right so in the first iteration i iterate through c right if i push c on the stack let's say this is the bottom of my stack if i push c on the stack it's right here then followed by that i push b on the stack now b is on top since b is on top i know like the next top level iteration of this while loop i would remove b and that's going to be the next node i visit and so they're really both depth first reversals nice so two things to note you're definitely going to use a stack to implement depth for reversal and you can use the stack in a few different ways right so here i'm using like an explicit like array as a stack and i'm implementing this using some iterative code right so using a few loops right what you can also do is implement depth first recursively because i know any recursion uses the underlying call stack so let me show you how to implement that as well and when it comes to you know having all these different tools in your arsenal i would definitely practice both the iterative and recursive flavors we'll see that later on this course so let's say i wanted to solve the same problem but now recursively it's actually going to be a less code so i'm going to have the same sort of arguments here i'm going to have the graph which is the adjacency list as well as a source node consider like the source node as like your current location so if i'm at some node maybe the first thing i should do is just print out myself right print out this node so i'll do is console.log this source node and that feels good just from the get because when we actually do a top-level call to this recursive function they're passing in a as the source node so i do want to begin a as the first node in my print and then from there i need to look at a's neighbors well if you want to look at ace neighbors like before just key into the graph adjacency list using that node right and this would give me an array of c and b now i just iterate through that array so i'll say 4 let neighbor of that array and at this point what i want to do is now do the recursion right so i make a recursive call on each of these neighbors so for me that means just call depth first print you give the same graph right the graph object doesn't change but you should change like the source node now you want to pass in that neighbor as the source node and you're going to make a recursive call for every neighbor in that array this would actually be all we need let's go ahead and just run this version give that a run over here it looks like now we get the order ace bdf and that's really again another type of depth first print right it's not exactly this order because this time we chased c first right we went a c e if i wanted to get exactly this ordering in my recursion then i would have to put b first right really same sort of pattern though let's give that another run good abd fce one thing i want to bring up about this recursive depth first is it has no explicit base case meaning there's no obvious like if statement that just like returns like you typically see in most recursion that's because in this problem i have an implicit base case when a node like e is a dead end right let's say my current source coming in is e well then when i iterate in this for loop i'm iterating through this empty array that means i have zero iterations if you have zero iterations then you never make a recursive call right so that's the same thing as having a base case right a base case is really just a scenario where we don't have a recursive call so that's how this code still works all right so now you know how to implement depth first in two ways right iterative and recursively and they both use definitely a stack let me now show you how to implement your breath first right so i'll comment out some of this code now we'll do a nice breath first give myself some room over here so for a breath first we'll want to solve this one iteratively and it's really only possible iteratively right because i know a breadth first traversal demands a cue if you try to like implement a breadth first reversal using some recursion then under the hood there's some stack data structure that's going to fight against the queue order that you want right so for breath first reversal you're always typically going to be writing some iterative code so some loops right let me define this i'll say breath first print take in the full graph adjacency list as well as the source node and i want to initialize my queue with that source node again the queue here is just going to be an array in javascript so i'll say const q equals an array that begins with just the source node awesome i'm going to use this q by just committing to two specific methods on my arrays in javascript so if i use array.shift that removes the first element of an array if i do array.push that adds to the last position of an array and using those two methods in combination would give me a nice cue where i add to one end and remove from the other end so like before we're gonna have a while loop and we're gonna iterate while our q is not empty and so while q dot length is bigger than zero nice and same thing as our iterative you know depth first you want to start by just removing the front of your queue so i'll say q dot shift that will remove the first element as well as return it to me so i can save in a variable i like to call it current just like the whiteboard right and then from there maybe i'll print it out so i'll console.log this current node and from here just consider your neighbors right so if i key into my graph using this current node that would give me an array of its neighbors i want to loop the reach of those neighbors so i can say four i'll say let neighbor of that array and for that neighbor i want to add them to the back of my queue so for me that would mean simply q dot push i'm going to go ahead and push that neighbor awesome so i remove from the front and i add to the back so that looks pretty good let's go ahead and give it a run and actually before i do that i'm going to change the order of this i'm going to put the c and b again it doesn't really matter the relative order of your neighbors i just want this exact output we'll talk about why that is right give that a run so i get acb edf just like i expected acb edf right so let's say we're on the first iteration of this breath first print i know that i would have just removed a because i initialized a on the queue right so my current is a and i print out a and then from there i start iterating through this array right so in the first iteration i have c that means i put c into my queue right and then afterwards i put b if you put c and then b that means c is at the front of the queue which is why on the second iteration i have c first all right so that's how you can manipulate potentially the lateral order of a breath first print awesome and that's all there is to this traversal algorithm what i really want to emphasize is especially if you look at the apples to apples iterative code you compare your depth first versus your breath first it's almost identical code you're really just changing how you access items in your array right you either pop or push or you shift and push other than that the whole like structure of this code is identical right all right so that's our introduction on depth first and breadth first for our graphs in the next section we're going to start to solve a problem right which will be really fun by just utilizing this code as our baseline tool and in that section i also promise to start doing the analysis for big o of these algorithms so let's jump back to that whiteboard hey programmers welcome back right now let's go over the approach for this has path problem so in this problem we're going to take in an adjacency list representing a graph for this problem and really all graph problems you definitely want to visualize this one with a picture and so what we'll do is we'll interpret each key of this adjacency list as representing a distinct node and if i look at any particular list i can see that this f node should point to g and i and they do tell us in this problem that i have a directed graph so i'm going to draw arrowheads on these edges here so f points to g as well as f points to i and i'll create similar edges based on the information in the given graph so i end up with an image like this and so they tell us that this is a directed graph that explains the arrowheads but they also tell us that this graph is acyclic so if you're unfamiliar acyclic just means no cycles that kind of begs the question what is a cycle in a graph so a cycle would be some path through nodes where i can end up where i once started in other words if i started at the a node over here then i can go to b then from there i can go to c then back to a and so on and so forth so if i did a traversal on the cyclic graph i would get an infinite loop what they're saying is our graph input is guaranteed to be directed so it has arrowheads but also acyclic so we won't have to consider any infinite cycles here that being said in this problem we also want to take in not only the graph information but also a source and destination node what we want to do is return true or false indicating whether or not we can travel from the source node to the destination node in other words is there a path that exists between those two nodes for this problem you can use either a depth first or a breath first search to actually solve the problem here i'll trace through in this approach video just the depth first search but in the walkthrough i'll be sure to code it up both ways so let's say i started at my source node i know that if i was doing a depth first reversal i can either choose the i or g let's say i happen to choose the genex now i have no choice right if i'm doing truly a depth first i should go deeper to the h so then i hit this h and as i traverse through these different nodes i need to ask myself if my current node is equal to my destination so far that hasn't been true at this point i've bottomed out with my h node i can't travel any deeper so now i can move laterally to a node like i at this point from i can either move to a k or a g let's say by luck i just happened to go to the g this would actually bring me down a path i've explored previously which we can optimize later on but wouldn't be too much of a big deal eventually if i continue this depth first search through the graph i would end up at a node that matches my destination at which point i can return true signifying that there must be some path from f to k just doing a depth first search and as we do the depth first search it's really important that you obey the directions of your arrows so i should never try to travel upstream so that was a scenario where we were able to find a path from source to destination that's why we returned true let's reset and say that now i should return false alright so let's say my source was j so i start at j and i'm trying to get to my destination of f if i start at a depth first reversal here sorry my j node travel to the i node at this point i can hit either the grk let's say i happen to hit the k at this point i've bottomed out so now i can move to the g and then from there to the h and at this point there's actually nowhere else i can go right so if i finish my traversal or through the graph using either a depth first or breath first and i never hit my destination then i can just return false right it must be the case that there is no such path from my source to my destination when it comes to implementing the depth first and breadth first reversals on this graph it's going to be exactly what we're used to you can either use a stack and solve it recursively or you can do it iteratively and use a q in which case you'd be doing the breadth-first traversal if we talk about the complexity of this let's say that n is the number of nodes of our graph a common thing that you can also do with these graph problems is define e as the number of edges here an edge just refers to a connection between two nodes basically just the arrows so if we use these two terms of number nodes and number edges we would have a time complexity of o of e o of the number of edges that's because we would have to travel through every single edge of our graph here the space complexity would be based on the number of nodes right if i solved it recursively or even iteratively with some sort of a depth first stack then the worst case i would have to have every single node on the stack right likewise if i solve it iteratively with a breadth first they would have every single node on the queue so that's just one way we can define the terms for analyzing the time and space of this graph typically for graph problems another acceptable way to analyze the time and space of your algorithm is to just use a single variable and just define n as the number of nodes that's because if you say n is the number of nodes then we can also say that n squared would be the number of edges remember that big o is about the worst case let's imagine the worst case graph let's say i just had these nodes of abc well if i wanted to create as many edges as possible how would i just create a single edge well an edge is just a connection between two nodes so you could just really draw an edge for every pair of nodes in your graph something like this and that's why we can say that n squared is the number of edges of any particular graph and so if you just wanted to use n to define the complexity here then you could say that your time is going to be o of n squared your space complexity would still be o of n do note that these are both two valid ways for defining the complexity for very typical graph problems now that being said i think this is pretty straightforward let's hop into the walkthrough video where we'll actually implement both a depth first and a breath first solution for these i'll see you there hey programmers alvin here right now let's go over a javascript solution for this has path problem and so we'll jump right in we're going to start by solving this one using a depth first reversal which i know requires some underlying stack data structure i'll just implement it using recursion so i can leverage the call stack to get my ordering and so i'm going to solve this recursively i'm going to consider my source argument as like my current position during the traversal and so i can have a base case and check all right if my source is equal to my destination then i must have found the thing i'm looking for so just return true this base case signifies that i found my destination so there must exist a path and so i return true always paying attention to the type that they want us to return for this function let's say it's not true well then i need to keep looking so what i should do is consider my current node which is source consider its neighbors if i key into my adjacency list i know that this is going to be an object so if i key into it using my source that would give me an array of all of its neighbors so for example let's say i was staring at this one if my current source was f and i say graph square bracket f i would get back an array of g and i so now i want to look through the neighbors right so what i can say over here is turn this into a loop and say 4 let neighbor of [Music] those neighbors i want to traverse to them which means i call recursively right call has path keep your graph the same but update your current position now i'm going to be situated at the neighbor and the destination stays the same i always have the same goal to get to i'm solving this one recursively so think about what type this is going to return i know it's going to give back boolean right it's going to tell me whether or not there is some path between my neighbor and the destination right so if there's some connecting point or some connecting path between my neighbor and the destination then i know that there must be some path from my source to the destination because your source is definitely next to your neighbor right so there would be a path between all of us and so what i'll do is check if this recursive call returns true i'll make it explicit here maybe it's clear and so if there is some path through my neighbor to the destination then i can return true just pass that true upward because once i find a path you can just exit out and return that true all the way back to the top level caller but let's say that this call returned false that means that there is no path through my neighbor to the destination but it could be the case that some other neighbor is actually going to work out and so what i don't want to do is just say like else return false you should be able to immediately catch that code like this is suspect because there's no point of having a for loop then right if in either case you're always going to return then you're never going to have a second iteration of this for loop right so if i don't find a path through my neighbor so if this call returns false then that's okay just continue on to the next iteration and search through your other neighbor that begs the question where should we return false it needs to be after the for loop so only after i search through all of my neighbors and i never find a winning path should i return false that would be our nice depth first traversal let's give that a test run awesome there we have it one thing to bear in mind here we are leveraging the assumptions in the problem right they tell us straight up that the graph you're going to be given is acyclic so there are no cycles so that's why in our code we didn't really worry about getting trapped in an infinite loop in our upcoming problems we'll have harder graphs that actually deal with that cyclic case but for now this is a good baseline solution while we're here let's also do a breath first solution which you know by now should be iterative right there's no way to do like a breath first um recursively and so i need to create my own cue so i can create a cue kind of in a pinch i always just use an array in javascript i'm going to initialize that q with my source on it so i'm going to refer to like source and destination they're really nodes but in the context of like our problem they're really just given as strings but they represent nodes right so think about the information they represent i'm going to iterate while my q is non-empty so while q.length is bigger than zero should be familiar code very similar to our tree algorithms and i start a single iteration of breadth first by removing the front of my queue so i can say q dot shift so move the front i can call that my current node that i'm traversing through and now that something has left the queue typically here is where i check i can check all right if that thing i just visited if that is my destination then i can just return true right i found the thing i'm looking for so there must be a path that connects my original source and my destination nice but let's say this was not true well then i need to consider its neighbors so like before to look at the neighbors just key into your graph using the source i can say graph square bracket source that gives me an array of all of the neighbors all the neighboring nodes so what i want to do here is iterate through every neighbor over there [Music] and then i can just add them into my queue so q dot push that single neighbor and do be sure to implement your true breath first so you need to make things leave from one end of your queue and you add to the other end so this code's looking good so you should realize how similar this is to our old like binary tree breath first except now we have to account for the fact that we could have like a dynamic uh amount of neighbors here not just dot left and dot right so i'm just iterating through all those neighbors and adding them i need a way to return false and you guessed it the move is after you finish this entire while loop if your queue becomes empty then you must have explored as far as you could and if you never return true then now you can return false because it must be the case that there is no path between your original source and your target so let's give this a test run we'll have a very similar time and space complexity but this would be the code for all of my iterative fans so here i'm getting a little error let's see what we did wrong here so it looks like i timed out here let's debug this one together if i had to guess that means i did something wrong getting trapped in an infinite loop this condition looks okay right q.length greater than zero and so ah here it is must be the case that i'm not correctly iterating through the neighbors here i just wrote source instead i need to say current because now i'm doing this iteratively right so whatever node has just left my queue i consider that node's neighbors and add them to be visited next through my cue so let's give that a test run honest mistake there cool and there's our breath first solution for this has path problem so what i want you to do is practice both the depth first and the breath first like you expect we're going to do a lot of graph problems coming up and depending on you know what the problem is asking sometimes we'll prefer one type of algorithm over the other so it's really important that you practice both of these algorithms now while the problems are relatively easy so practice this give it a shot on your own and i'll catch you in the next problem see you there hey programmers alvin here right now let's go over the approach for this undirected path problem so i'll jump right in in this problem we're going to be given an edge list for a undirected graph so if i'm familiar with the terminology here really what we're saying is every pair in this edge list represents a connection between two nodes for example if i look at the first edge in the edge list i see i comma j that means that there's a edge or connection between i and j and since this is an undirected graph not only can i directly travel from i to j but i can of course move from j to i so it really represents a connection in both directions and so as we start to attack this problem i want to do is actually convert this edgeless into a more favorable format like an adjacency list that's because typically when we perform our traversal algorithms they work best on an adjacency list form so let's start by doing that conversion here that'll actually be pretty easy to code up so i want to basically generate a graph where i have nodes as keys and i want them to point to an array of their neighbors for example if i wanted to convert the first edge into an adjacency list form what i can do is create keys for i and j i know that i is a neighbor of j and also j is a neighbor of i so i'm going to populate those neighbors respectively now i'll just follow this process for another edge so if i look at the edge k comma i i need to create a new key for k and i'm going to populate that with i and then for the existing key of i i just add k into that collection so do you bear in mind the most important thing about this conversion is because we know that the graph is going to be undirected whenever you put a connection within your graph make sure that you have the inverse connection so if i have an edge from k to i i also need to have information for i to k and this process would just continue for the entire list of edges and by the end of this conversion we'll end up with an adjacency list just like this and now we're ready to perform our main algorithm when we go through the code walkthrough for this i'll show you in depth how you can actually create this adjacency list and so when we want to actually come up with a traversal algorithm to solve a graph problem it really helps if you actually visualize the shape of your graph so i actually want to visualize this in terms of nodes and edges so that means a bunch of circles and lines between them so if you drew out a nice picture for this graph information you would end up with a diagram like so and so we'll go through the rest of this approach video just referencing this diagram something important i want to bring up at this point is for this graph a very common case you'll have to handle is what if your graph has a cycle and that's especially true for your undirected graphs and so just for the purposes of this approach video i'm going to add an additional edge just so we can talk about an explicit cycle so i'm going to add one new edge from k to j cool the reason is now there's a nice big cycle of length three highlighting it in red right now and this cycle is important to watch out for because if we don't do any special handling we may get trapped in an infinite traversal so imagine i started at this k node and next i moved to j then i would move to i and then back to k and then back to j and then i and so on so that would give me a cycle we'll have to guard against that and so i can have a cycle of three nodes here right and you can really have a cycle of basically almost any size as long as it's more than one so for example if i took a look down here notice that my graph actually contains technically like two separate islands but we would consider them as just one giant graph right so if i look at the small island of o and n they actually form a trivial cycle right if i start a traversal at o from there i can move to n and because i know that the edge between o and n is bidirectional right it's an undirected graph that means i can travel back to o and then back to n and this would give me cyclic behavior so i have to watch out for all types of cycles in this problem so in the context of this problem not only are we given a graph we're also going to take in a two nodes so let's step through an example w