Depth-First Search

[00:00:00]
>> So now, we're gonna go A, B, C, D, E, I wanna say, F was down here, G, H, I, there we go. I think I just created the exact same graph, fantastic. We created the same graph. All right, so now, we're gonna do a depth-first search. All right, so depth-first search is kind of like the opposite of a breadth-first search, it uses your stack as a way to maintain things.

[00:00:33]
So last time we used a Q for a breadth-first search, I know Q is not spelt with 1Q, but it's just easy to write that way. Depth-first search is gonna use your recursive stack, you can technically just use a stack, and then keep track of where you're at and added pushed to the stack.

[00:00:48]
If you need to really be caring about optimizations in like a compiled language, that could be a really awesome way to avoid things. In-lining it I think pretty much yields the same operation. I don't know I have never tested, but with the depth-first search, we're gonna start here, and then, we have to have some rules, right?

[00:01:02]
So my general rule is that, I'm gonna start and I'm gonna always add things from top to bottom, okay? Makes sense, so that means, we start with A, is our starting node. Well, I'm gonna have to go over each child, right? For each child, we need to visit that child, right?

[00:01:17]
So now, I need to go visit each child. Whatever that child is here at C, there we go. So we're gonna have to kind of do that thing. So I'm just gonna try to iterate them in correct item, which means, we're in-function visit right here, which means that we're just gonna recursively call it.

[00:01:31]
So A will be visited. And then that means we're gonna have to add B and C, but since it's recursive, we just go to B, B will then be visited. Now, we do B's children, which Which is D and A. A has already been seen, D will be next.

[00:01:43]
So now we visit D, and now D starts going with its children. We'll go this way. We hit B first. We've already seen B. Therefore, we're gonna go to C. C will then be visited, and then, we go to F, F will be visited next. Then we'll go to G, G will be visited next.

[00:01:57]
Then we'll go to H, H will be visited next. Then we'll go to E, E will be visited next. And then, we kind of have to do this whole unwinding for, wait, hold on, whoa, whoa, whoa, whoa, I went into breath-first there for a second. We get to H, H has children, so therefore, we're gonna go to I, I has no children, we walk back once, we go to H, H has no more children.

[00:02:15]
We go back to D, D has more children, E, now, we visit E, E has no children, go back to D, D has already visited all their children. And go back to B, B now has visited all of its children. We go back to A, A has now visited all of its, or not all of its children, it tries to visit C, C has already been visited.

[00:02:29]
We go back to A, we're done. Okay, so you kind of do it in the recursive style. That's a depth-first search, so what is the runtime, of course? You have to visit everything, you have to traverse every single node. So that's a classic, that's the classic E+V, right?

[00:02:43]
But E is larger than V, everyone knows that. So therefore, you just say E, E's fantastic. Same thing with breadth-first search. Now, there's a pretty neat application you can do with depth-first search. Let's pretend for a second that this is actually a directive graph. All right, whoopsies, wrong direction there.

[00:03:06]
And this happens to be your module graph. Like this is how you built your program. These are all files and A requires B and C, which requires D, D requires E, H, G and F, and H requires I. So, if I were to start at A and do a depth-first search in post order traversal, right?

[00:03:27]
Meaning, I add them after I'm done visiting every last possible child, I will actually come up with your module graph or this is known as topological sort. We're gonna sort them in the order in which we visit them last. So, we start with A, we go to B, B goes to D, D goes to E, there's no children left.

[00:03:50]
E, all right, we come back to D, D goes to H, H goes to I, there's no more children. I, we go back, there's no more children for H, we put an H. We go back to D, we visit G, there's no more children, G. We go back to D, go to F, there's no more children, F.

[00:04:11]
We go back to D, and now we're like, okay, look, notice that it's directed towards D, we cannot take this path backwards. No more children left for D, we load in D, we go back to B, there's no more children left for B, we put in B. We go back to A, A still has a child left, C, we visit C, D's already been visited, no need to do that, and then, finally, we end back at A, no more children left, this would be it's topological sort.

[00:04:34]
Now, you can technically start at any node, and it will produce slightly different variants of this, like if we were to start at H, we would get I than H, which is slightly different here. But then we'd have to pick another node, we'd have to go say to B, and then B would produce most of the rest of the graph and end right here, then we do a which would produce C and then A.

[00:04:55]
And so, there might be slight different ordering, cuz you can imagine that C could be in place of B, B could be in place of C, depending on how you choose which child to visit or how they're stored in what order. Just wanted to show you that, so this is called topological sort, pretty neat.

[00:05:08]
I thought it was pretty neat, good times, right? You get, you can use this. So if you had to build Webpack really quickly, you might need to do a little topological sorting. There you go, okay? So, introduction to graphs, everyone's feeling pretty good right now, or feeling happy about it?