Data Structures and Algorithms in JavaScript

# DFS Graph Stack Trace Part 2

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "DFS Graph Stack Trace Part 2" Lesson is part of the full, Data Structures and Algorithms in JavaScript course featured in this preview video. Here's what you'd learn in this lesson:

## Bianca continues tracing through her traversal of a Graph using the newly implemented traverseDepthFirst() method.

Get Unlimited Access Now

Transcript from the "DFS Graph Stack Trace Part 2" Lesson

[00:00:00]
>> Bianca Gandolfo: Because we're traversing, we are now going to put some more on our stack. Our current,
>> Bianca Gandolfo: Where we passing or something. So our first value is neighbor, and our visited array has two things in it.
>> Bianca Gandolfo: Where did it go? Did I erase it?
>> Bianca Gandolfo: Here it is.

[00:00:30] I just didn't comment it out. So our visited array now looks like this.
>> Bianca Gandolfo: Right, our distance is now what?
>> Speaker 2: Two.
>> Bianca Gandolfo: Two? Yep, and we're going to run a function on the value. What's the value that we just passed in?
>> Bianca Gandolfo: What did we pass in?

[00:00:57]
>> Speaker 3: Four.
>> Bianca Gandolfo: Yep, four. Foo, our visited array has some stuff in it, right? And then our distance of 2, right? 1 plus 1, 2. Okay, so now we're going to add our value to our visited list. Comma 4, true. And again, we're going to loop through all of the values, adjacency list, array, right?

[00:01:35] So we go to 4, and check 5, so neighbor's now 5, we're going to check it. It doesn't exist yet in our list.
>> Bianca Gandolfo: So we're gonna skip that, and then we are going to keep traversing all the way down.
>> Bianca Gandolfo: Okay, all the way down. So now, I'm just gonna do this really quick.

[00:02:12] So we pass our visited in there.
>> Bianca Gandolfo: So just so we know, when we pass 5, we pass foo, we pass our object.
>> Bianca Gandolfo: And then we pass 3 as our distance. So our distance is now 3. We're console logging 5, which is our current value. We're now adding 5 to our visited list, right?

[00:02:36] The reason we do it after this, is because, once we call the function, we consider that visiting.
>> Bianca Gandolfo: And then, we're gonna loop through its neighbors. We're going to look at its first neighbor, which is 6, has not yet been visited, so we're gonna call it here. So the neighbor, we're going to pass 6, and we're going to pass foo, we're going to pass our visited object and then our distance, which is now 4.

[00:03:05] And then, we're gonna go all the way, all the way down to the bottom.
>> Bianca Gandolfo: So now, our visited array, I mean, object, looks like this. Our distance is now 4. We're gonna console log 6. And now, since we ran our function, we are going to set 6 to true, okay?

[00:03:33] Now we're gonna loop through all of the nodes in 6's array, which is how many times are we gonna loop?
>> Speaker 2: Zero?
>> Bianca Gandolfo: Zero times, right? So we're not gonna enter into this for each, because it's empty. So just like any for loop, if it's empty, you're not going to run it.

[00:03:58]
>> Bianca Gandolfo: So we find ourselves at the end of the function. Since we're at the end of the function, it's just gonna return out of the function.
>> Bianca Gandolfo: It returns undefined, just automatically. And so, once we reach the end of a function when we're doing our stack frames like this, what happens?

[00:04:17]
>> Speaker 3: You pop it off.
>> Bianca Gandolfo: You pop it off the stack, absolutely. So we're gonna pop it off, we're gonna find ourselves here.
>> Bianca Gandolfo: Still in this for each loop, right? So we pass 6, right? And then, we're gonna see if there is another one. And since there isn't, we have no more things to loop.

[00:04:39] So we,
>> What do we do when we are done with the function?
>> Speaker 2: Pop it off.
>> Bianca Gandolfo: Pop it off, yeah, pop it off.
>> Bianca Gandolfo: And notice we popped off 5, we popped off 6, we popped off 5. Here we are, popping off 4, right? And the reason we're popping it off is because, there's no more neighbors, not because of the visited thing, right?

[00:05:08] We have, we're not going back up here and checking, if it's been visited or actually it's in here where we checked that. So we pop off 4, and then again, we pop off 2, that's where we're at.
>> Bianca Gandolfo: Then we're gonna come back into 1, right, our value is 1 here.

[00:05:33]
>> Bianca Gandolfo: And we have one more loop through. So we loop through it once, then that's how we went through all of that recursion. And now we're gonna check its second neighbor, which is 3. So here, we're gonna check if our visited object and also, just note that our object is, when we pass it around, we're actually doing work on the same object, so this object in here still has the things, all of the values in it.

[00:06:06] What was it? We had 2, 4, 5, 6.
>> Bianca Gandolfo: So just remember that.
>> Bianca Gandolfo: Where are we? Here we are. So we're going to check if 3 is in our visited object, which is, is not. So then, we're gonna traverse again.
>> Bianca Gandolfo: We are passing here 3, again we're still passing foo, we're still passing all of this.

[00:06:40] Actually, it also has 1 in it.
>> Bianca Gandolfo: Passing all of this, and then the depth plus 1, there is still 1, right? Cuz the depth here, even though we're passing a distance, because distance is a primitive value, it doesn't get past around like the object. So we're doing work on, the number is gonna change in each stalk frame, but the object is gonna stay the same.

[00:07:07]
>> Bianca Gandolfo: Cool? Are we okay with that?
>> Speaker 2: So the depth is from the initial value?
>> Bianca Gandolfo: Yeah, yeah. And if we wanted it to not do that, you could potentially save it in an object and then make sure that you're using the same object throughout, and then you could save it.

[00:07:28] But in this case, we don't wanna do that. And it make sense for us to just use a number. Okay, so recursion. No, recursion. So we're gonna call this on 3.
>> Bianca Gandolfo: This is still the same, our distance is now 1. We're gonna console log our value, which is 3.

[00:07:52] Now, we're gonna set this up, we're gonna add 3 to it.
>> Bianca Gandolfo: Right, and these all have true next to them, I'm just writing it shorter, so we can fit it. So then, we go to 3 and we're gonna loop through its array. All right, so first, we're gonna see if the neighbor has been visited right, which is 4.

[00:08:25] So we look up visited, visited, I can spell sometimes. And we're gonna pass 4, and we're gonna do a lookup on this object. What is it gonna return?
>> Bianca Gandolfo: For 4?
>> Speaker 2: True.
>> Bianca Gandolfo: True, yeah. So all of them are set here to true.
>> Bianca Gandolfo: So we have 4 in our breadcrumbs.

[00:08:54] So this returns true, so we're just gonna return.
>> Bianca Gandolfo: And since there's no other, nothing else in our array, we're just gonna return out of this entire recursion.
>> Bianca Gandolfo: And then, this is done too, there's nothing else.
>> Bianca Gandolfo: Then we are done.
>> Bianca Gandolfo: Depth first search, with a graph.