Depth First Search Solution

[00:00:00]
>> Bianca Gandolfo: So we are going to take a stab at Depth First Search.
>> Bianca Gandolfo: First things first, we want to understand how our graph data structure works. So in our constructor, when we instantiate our graph, we instantiated adjacency list, which is just an empty object. And when we wanna add a node, we need to make sure that,

[00:00:29]
>> Bianca Gandolfo: This is interesting.
>> Bianca Gandolfo: I don't want that. Okay, there we go. We add a node. We just set that node here to an empty array. So this is something to note that if our node is an object, and we're saving it here, this is gonna be stringified.

[00:00:53]
So if this is an object, you want to make sure that this is a map.
>> Bianca Gandolfo: Cool, awesome. All right, so let's check out our Depth First. So for Depth First, you just choose any starting node really, but we can pass it in. And let's start with, we can start with 1.

[00:01:19]
So let's pass in our starting node and our function will be this console.log. We're gonna instantiate our stack and we're also gonna instantiate our list of visited nodes. So first, we wanna push to the stack. So the stack keeps track of nodes that have been visited, but not what we call explored.

[00:01:45]
So explored is when we have gone through all of the children, and we're just done with it. We don't need to look at it anymore. So that's the difference. So the nodeStack will say this has been visited, but we aren't sure that we've explored it yet, okay? So we always are gonna put our node there, and so we will have, let me just make this the same.

[00:02:16]
Where we have our nodeStack. So we're going to start with 1, and our nodeStack here is gonna be 1.
>> Bianca Gandolfo: And we'll have to save it here as visited, so we say, we'll just add 1 there, okay? This is an object, but this is just,
>> Bianca Gandolfo: I don't know, just a node, it's not code.

[00:02:40]
So while the nodeStack.length. So while we have nodes that aren't, we have unexplored nodes, let's keep exploring, right? Once this is gone, that means we have explored all of the nodes in our graph, okay? So while nodeStack.length, let's get our current node and all its neighbors. Let's do some work on the current node.

[00:03:07]
In this case, we're just gonna cancel that log, whatever that is. And then for each of the neighbors we want to, if it's not visited, add it to our stack and then mark it as true. So let's take a look at that. So what is our current node?

[00:03:26]
1, so we pop it off.
>> Bianca Gandolfo: And then we're gonna console log it for each neighbor, right? So our neighbors are 2 and 5. We are going to, only if it's not visited. So first we check here, right? So is 2 visited, no. So it's not visited, so let's push it to the stack.

[00:03:56]
And then we'll push the neighbor to the stack. And also we are gonna be marking them as visited.
>> Bianca Gandolfo: Very good and then we’re going to keep going. So we’re gonna pop that off.
>> Bianca Gandolfo: The stack which is 3. So let's see. So, so far we logged 1.

[00:04:30]
>> Bianca Gandolfo: We're gonna get our neighbors which is 2 and 4, okay? And then we're gonna log our current, which is 3. For all of our neighbors, if they're not visited, let's check it out. So is 2 visited, yes. So we move on to 4. Is 4 visited? No so we're gonna mark it, we're gonna add it to the stack, and we will mark it as visited.

[00:05:02]
>> Bianca Gandolfo: And we'll go again. So we'll pop it off. So we'll go to 4.
>> Bianca Gandolfo: Here. We got all the neighbors, here are the neighbors. For each one, we are going to, if they're not visited, put them on the stack. So 2, 2 is visited, is 5 visited?

[00:05:22]
No so we'll put it on stack,
>> Bianca Gandolfo: And we're going to mark it as visited. Great, da, da, da, where are we? Okay, and then we're going to go back up here. Get the 5, here. We're popping that off the stack. We're going to get all the 5's neighbors.

[00:05:51]
>> Bianca Gandolfo: 4, is 4 been visited yes, has 1 been visited yes, has 2 been visited yes, okay. So we pop. We just move on with our lives, we're going to go to 4 again. Has 2 been visited? Yes. Has 5 been visited? Yes. Has 3 been visited? Yes.

[00:06:09]
So we had popped that off, and now we're back at 2. And let's see, have we visited, I think we have visited everything, awesome.
>> Bianca Gandolfo: So this is an iterative approach to Depth First Search. So in the recursive approach, you don't need to make an explicit stack, because your recursion is the stack.

[00:06:36]
But I like this because it's more obvious, and if recursion is making your head hurt, maybe iterative is a nice break from that. Cool.
>> Bianca Gandolfo: Questions?
>> Bianca Gandolfo: Mm-hm?
>> Speaker 2: Are there advantages to iterative or recursive approaches when it comes to time complexity?
>> Bianca Gandolfo: Let's see, no, not really.

[00:07:12]
So recursion takes up more space and memory, but it doesn't really matter that much for what we use it for. And also recursion's not optimized, completely. In some languages, recursion is really optimized. In JavaScript, it's not super optimized, so it's probably better to do iterative in general. But recursion, it's just fancier.

[00:07:44]
But again, if you are just dealing with small numbers and not doing data sciency type things, then it doesn't really matter.