Implement DFS on Adjacency List

[00:00:00]
>> Can we also do in order and post-order traversals?
>> I mean, technically, yes, I mean in order and post order traversal is literally just mean before you do the recursing or after you do the recursing. And so when we do the next item, which of course is gonna be a DFS on a graph list, meaning an adjacency list.

[00:00:19]
We are gonna do both a pre and postordering operation. You can in some sense do a pre or post, it doesn't have the same meaning. Cuz a pre or post-order traversal means you visit the node, do a recurse, or you do recurse, then visit the node. In a graph, we're gonna be building a path, which means pre, we visit the node, we put it in our pathway.

[00:00:42]
We go and recurse, post, we pop it from our pathway. So we're actually gonna do both a pre and a post-order traversal right here. So again, just like before, I'm gonna just fix this, because again who made this nonsense? Okay, again, let's not screw this up, there is a null if we don't find it.

[00:01:01]
We can't mess this one up. All right, so let's go function walk, and we're gonna do the exact same thing. We need a graph, right? We also need what node are we currently at. Oopsies, I gotta do this, weightedAdjacencyList. And then with the node that we're at, right, we're not gonna consider a source, right?

[00:01:20]
We're only looking for our sink or our needle, right? We're gonna have our needle, which has a number of what we're looking for, and then we need a scenery. Remember this, we did this before, we need a way to be able to know, have we seen this node before?

[00:01:36]
Awesome, and do we need anything else? Of course we do, we need a path, which is a list of numbers, correct? This is the path in which we have taken to get to this point. All right, but what do we return? Well, if you recall from the last time we did this, which was the maze solver.

[00:01:52]
So if you don't know, the maze solver and this problem are almost identical problems. They're effectively the exact same thing. You'll even notice that this really is starting to look exactly the same. All right, so if I go back here, go to day one and go to MazeSolver, and yeah, wait, I was already there.

[00:02:13]
MazeSolver, you'll notice that walk had our maze kind of like what our wall was, which was different, it has a current. It has our needle, it has our scene, it has our path. It's pretty much the exact same thing that we were just doing. There we go. So we have effectively the same thing, which means we're gonna need Boolean, right?

[00:02:36]
We're gonna need the null, if we've actually found the ending to this. All right, so again, base cases, always base cases when we're doing recursion, what are some base cases of this?
>> We found a needle.
>> We found our needle, beautiful. If (curr === needle), return true, right?

[00:03:00]
We found it, we're done. We've done exactly what we wanted to do, awesome, let's go. If we've already seen this, right, if we've already seen current, We don't wanna look this way, we're done looking, right? We've been here, the answer is not in this area, go somewhere else.

[00:03:20]
Awesome, all right, so now that we've done that, we probably need our recurse step. Now remember, it's broken into three things, previous, recurse, post. So previous or previous, pre, the pre-order, the pre-operation should be path.push(curr). We are now officially visiting this node, it is in our pathway to the potential end, let's add it in.

[00:03:44]
Then, the post step, we need to pop out that node, right? So long as we push, as long as every time we push, we pop, it will always maintain the order of the array in the path we took. So we should be good to go. All right, so now it's the recursive step.

[00:04:02]
How do we do the recurse? Well, the first thing we need is the list, so const list = graph[curr], right? Cuz remember, an adjacency list is going to be the graph edge, a list of graph edges. A graph edge is simply where it's going to and the weight that is associated with it.

[00:04:22]
Make sense, we're looking good? Awesome, all right, so we've either seen it or we've seen it, it's either our answer, or we have to recurse it, so there we go. We have a list, which if you look at it, it's just a list of graph edges, who is this node connected to?

[00:04:38]
And so now we need to do the exact same thing again. Except for, ooh, I did forget one thing, we need to now see current, right? We make sure it's false, then we flip it to true. We don't wanna mess that up, right, because, of course, this is recursion, this is not doing iterative.

[00:04:57]
Iterative I put the scene usually in a different area as we did with BFS, which is usually before we add it to the queue. And this one, we do the scene afterwards, after we've successfully passed the base cases, which makes sense. Because the base cases are a part of the loop in a BFS, right?

[00:05:13]
You'll notice that I go, hey, have we seen you? Hey, are you an actual node? Hey, we do that. So it's the same kind of idea. So there we go, we've seen it, we've pushed it, we have grabbed the list. And now we simply need to walk this list until either we find the needle, or we exhaust our list and return false.

[00:05:32]
So let's put the return false cuz that is obviously the easier of the two answers. And now let's go for let i = 0, i has to be < lists.length ++ i. We always use for loops, we don't do the kind of the array methods, because you have to be able to return or break out of often an algorithm.

[00:05:50]
So those kinda convenient functions just aren't an option in this world, and this means not an option. I don't know how I got this hand gesture, it's just part of talking and moving the hands. Okay, so if (list [i], let's go like this, let's create an edge, right?

[00:06:07]
Make sure you name these things easy, cuz where else are you gonna get all of your values mixed up in your head. All right, so we have an edge, so if, not checker seen, if(walk(graph, then what's our current? What is our current going be? Our current, of course, is going to be the edge, right, edge.2.

[00:06:28]
Now, we're looking for the needle, needle, and then what are the other items? Have we seen this? And of course our pathway, so there we go. So if we successfully walk this path and find the needle, therefore we need to break out of this. We have found it, we're good.

[00:06:45]
But there is one problem to our breaking. If we return true here, do we have the end in our path? No, we don't, so we can either move that check below the path right here to maintain recursion. Or we can just do another way, which I also think is kind of easy, just simply pushing edge.2 right?

[00:07:08]
Just throw it in, right, we're gonna throw it in, post it. You can do either way, I like it this way, that's good enough for me. So instead of breaking though, we don't wanna break, cuz of what happens? We pop, we return false, bad. Return true, there we go.

[00:07:23]
So that way we can send the signal back up the recursive stack, so that each place pops. That makes sense? But I don't really like this, I feel like I'm gonna get a bug. So what I'm gonna do is I'm actually gonna remove this, I just feel like that's gonna turn into a bug.

[00:07:38]
I just feel it, feel it, we are gonna put this right here, and I wanna maintain that perfect. There we go. Yeah, why don't I just do this? There we go. I don't know why I didn't do that. So there we go. If we have the needle, then we returned true, we just wanna make sure we put the needle in.

[00:08:00]
If we do it down here, I'm afraid that we're gonna get a whole bunch of additions that I don't want to do. And so I don't wanna reverse add all the path back in, so we would actually double add everything. Saw that one coming, saw it coming from a mile away, and there we go.

[00:08:14]
We've now officially done the walking. We use our pre-step to be able to push the path and create the structurally correct path. We use the pop at the end if we never found that path in this branch of the graph. All right, so now all we need to do is just simply call this function.

[00:08:30]
So of course, const seen equals a boolean array, right, which equals new array, which is gonna be what, (graph.length).(fill false), right? This is just the work part, right? Path, which is gonna be a number array. Awesome, okay, we kinda got this, right? So that means all we need to do now is, what did we call this thing, walk?

[00:08:56]
Okay, we called it walk. Walk, and now we need to pass it in, what is it? And to do graph, our source, where we want to start from, our needle, seen, path, there we go. We walk all the way there. And of course I created this again, just a stupid interface.

[00:09:15]
If (path.length ==0) return null, gosh, what kinda programmer am I? Return path, an empty path would have been perfect. So there we go. So long as I've done this correctly, I should be able to DFS graph, and if this is correct, okay, we're only running the first one.

[00:09:34]
Boom, we got it, awesome, so we did just depth- first search our graph, and returned the path from the source to the needle. Now, the real question is, what is the running time of this? Well, if you think about it, if you think about it, what's gonna happen is that every single node, if the very last node we check is our needle, right, that would be the worst case or actually, the worst case is our needle.

[00:10:01]
There is no path to our needle cuz the needle just doesn't even exist on a graph. But assuming we're given a valid node, it'd be the last one that is searched, meaning that we will check every single edge once, right? Because then we'd have to have a separate edge this direction, which we'll check that once at every single node.

[00:10:20]
We will also visit every single edge or node once. We will never visit a node more than once, correct? Well, I mean, you could argue, well, actually you call a function when you do the depth-first search, which does this. And the breadth-first search, you do the scene check first.

[00:10:35]
So maybe, maybe, maybe, well, yeah, okay, so maybe you could say, you could check every node in some sense twice, maybe. But the reality is what you're gonna be doing is you're gonna be searching a V + E, right? You're gonna check every single vertex and every single edge, there you go.

[00:10:53]
So that is our running time really, it's fantastic. We did it, we figured it out, awesome, we've done it. We're the fastest, smoothest, greatest searchers of graphs and matrices, but then, my goodness, they're like, this is just terrible. You can tell me it exists, but I want the shortest path there.

[00:11:11]
I don't want to have to walk the whole dang graph, I wanna be able to do the fastest walk there. So you can imagine the Internet, it doesn't just take our path from your house to say England. It's gonna take the best path from here or likely the best path.

[00:11:26]
Maybe there is some level of error, I don't know what the level of error is in the Internet graphing, but I assume it's pretty dang perfect.