Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "DFS Graph Stack Trace Part 1" 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:

With the traverseDepthFirst() method implemented, Bianca tests it out by tracing out each step as it traverses a graph. With each iteration she duplicates the code and adds comments for what the next recursive call would be.

Get Unlimited Access Now

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

[00:00:00]
>> Bianca Gandolfo: Let's get picture of our adjacency list for reference, okay. We're just gonna say, myGraph, right.
>> Bianca Gandolfo: Equal some new graph. And then let's just pretend we do all the operations to build our graph.
>> Bianca Gandolfo: Let's move this like this. We're gonna move this like this. All right.

[00:00:28] So now we have myGraph, and we're gonna run myGraph.traverseDepthFirst, traverseDepthFirst.
>> Bianca Gandolfo: Just like this.
>> Bianca Gandolfo: Cool, and let's do it.
>> Bianca Gandolfo: Actually, let's give it a value. We'll start with 1, and then we'll have some function, we'll just call it foo, cuz I'm not creative at all. Okay, here we go.

[00:01:08]
>> Bianca Gandolfo: All right, I'm gonna skip this to save us some space.
>> Bianca Gandolfo: And we're gonna copy this. So the first time we come in here we're gonna initialize visited to an empty. It's gonna be initialized cuz we haven't passed visited. We're checking here if we have passed it.

[00:01:30] Since we haven't, it's gonna be empty. The distance is gonna start off at 0, cuz it's our very first one. We're gonna call our function on there. And let's just say we're gonna console.log, the value of something. And it's just gonna log one. Good to go, now visited value equals true.

[00:01:53] So what that's gonna look like is this, right? Our value is 1, we're setting it as true and that's what visited now looks like. Okay, so now we're gonna do this forEach. We're gonna loop through. And the way that forEach works is it's gonna loop through each item in a collection.

[00:02:15] In this case, our collection could be an array. And I think, yeah, it's an array in this implementation. So for each element in our array, we're going to run this function. And we're gonna call that element, neighbor, right? And the reason we're calling it neighbor is because this is our adjacency list.

[00:02:35] So everything in our adjacency list is considered a neighbor. So for 1 in our adjacency list we have 2 and 3, and in this for-each loop we're going to be looping first through 2, right here, okay? So, here we go. First we're gonna check if it's been visited, so for the neighbors we're saying visited 2.

[00:03:07] And this is gonna return what?
>> Bianca Gandolfo: Undefined.
>> Bianca Gandolfo: Cuz we haven't visited yet, it doesn't exist. So since it returned undefined, woah, craziness. Since it returned undefined, we're not gonna enter into this. We're going to traverse. So here, this is referring to our entire graph, right? So we're gonna traverse.

[00:03:42] We're gonna pass 2. So here's our recursion. So we're going to paste our entire internals over.
>> Bianca Gandolfo: Cool. So the things that we're passing, we're passing neighbor, 2, our function, foo. And then visited which is our object, right. That what's it looks like. And then our distance plus 1, which is 1.

[00:04:13] Okay, so those are things we're tracking for each recursive call. And here we go. Visited, we're gonna either pass it or set it. Since we passed it, this is what visited looks like.
>> Bianca Gandolfo: Distance is now gonna be 1. We're gonna call our function or whatever, and maybe that's gonna console.log, 2.

[00:04:36] We're just imagining that's what foo does, it could do anything. And then now we're going to add a new element to our visited object. So now the current value is what?
>> Bianca Gandolfo: 2, absolutely. So our current value is 2. So we're gonna add it, and we're gonna set it as true.

[00:05:02] And now you can see how it's kind of like bread crumbs, cuz you're remembering where you've been previously. Cool. So this, right, is still gonna be our graph. And then here's our node list values. So we're looking at 2's adjacency list and looping through it with this forEach, okay?

[00:05:26] And each neighbor is gonna be one element in forEach's array, or if it's a linked list or whatever, however you're going to save it. In this case we're using an array, okay. So the first thing we're gonna do is we're gonna see if that neighbor has been visited by checking in our visited object.

[00:05:56] And the first neighbor of 2 is 4. Has it been visited? No, cuz it's not here yet. So, if we look up visited 4, it's just gonna return undefined, right? So that's gonna be false, and we're going to then traverse because it hasn't been visited.