Depth First Search

[00:00:00]
>> Bianca Gandolfo: So let's dive in. So let's start with depth first. And we'll see, as we're exploring this graph, we're gonna go down, down, down, all the way down to the end. We'll go to the deepest, and we come back up, and we go deep again, and we come back up.

[00:00:18]
That is essentially the path that it's gonna take. However, as usual, this graph or this diagram seems easy. But it's a little more tricky than just like putting lines, filling in circles with numbers, right? It's always a little trickier than that. So let's talk about,
>> Bianca Gandolfo: The method about how we would do this.

[00:00:54]
So whenever someone ask you what's the difference between depth for a search and breadth for a search? What you are going to say is that, depth for a search uses a queue, sorry, depth for a search uses the stack, breadth for a search uses a queue. You're gonna ask someone that, and they're also gonna tell you the same thing.

[00:01:17]
So fun facts, so we're gonna use a stack and as we are traversing through our graph, we are going to add things to the stack. And we're gonna mark vertices as visited. If the vertex has unvisited children, you add the unvisited ones to the stack. And then you keep going in this recursive method.

[00:01:46]
And then if it has no unvisited children, we're gonna pop it, and you're gonna repeat until your stack is empty. Once your stack is empty that means you have visited all of your vertices. And the reason that you wanna mark as visitor, cuz you only wanna visit them once, so once have visited something, you won't visit it again.

[00:02:12]
Otherwise, you can kind of get stuck in like loops and stuff. Since graphs are not hierarchical, you can be going in a circle for a while, so you need to just keep track. All right, so what does that really mean for us? So we start with this, and we visit.

[00:02:33]
We add it to the stack, we mark it as visited, then we go down. 2, added to the stack, mark it as visited, down to the child. 5, put it in the stack, mark it as visited. 9, 9 has no children. But first, we have to add it to the stack, mark it as visited.

[00:02:59]
So then we pop off or return from a recursive call. And so we see the next thing in the stack, which is 5. We see if there are any more children, and there aren't, so we're gonna pop that off as well. Again, pop it off until we get back to 1 which does have unvisited children, right?

[00:03:28]
So we're gonna go to the next unvisited child. I'm going backwards. Next unvisited child which is 3, and then put that on the stack, mark it is visiting. Notice that the stsck is dynamic but the visited list persists, that's important. And so we go to 6, 6 has a child of 10.

[00:03:53]
So it's pushed 6 the stack, mark it as visited. We go to 10 push it to the stack, mark it as visited. 10 doesn't have any children, so were gonna pop that off the stack to 6, check if 6 has anymore unvisited children, it does not. 3, check if it has unvisited children, it does, 7.

[00:04:15]
We’re gonna put 7 on the stack, mark it as visited, pop that one off cuz it’s empty. We get to 3, we now have visited both of its children,a nd pop it off and we're gonna go to 4. We're gonna keep doing that adding popping it off until we have visited all of the nodes.