Data Structures and Algorithms in JavaScript

Depth-First Search with a Graph Solution

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Depth-First Search with a Graph Solution" 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 looks and the final JavaScript solution for traversing a Graph with a depth-first-search. The code for the solution is located on the "solutions" branch in the Github exercise repository. Search the code for the Graph.prototype.traverseDepthFirst method.

Get Unlimited Access Now

Transcript from the "Depth-First Search with a Graph Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: We are going to quickly, quickly, quickly go over depth for search and breath for a search with our graphs. And then we're gonna jump in the harsh tables and then we're gonna do a summation of the entire workshop and sort out next steps armed with what you know what's the next battle.

[00:00:24] Cool so here's our depth for search procedure. So here's the procedure where we're marking with colors. So the first one is you wanna mark this discovered. And then for everything that's unvisited visit them.
>> Bianca Gandolfo: And then mark it as explored once you have visited all the way down, cool?

[00:00:49] So we did some experimental pseudo code. I left you with some questions which I'll answer when we explore the solution, which we'll do now. Good morning. Here we go.
>> Speaker 2: Could you move your mic up a little bit?
>> Bianca Gandolfo: Sure, sure.
>> Speaker 2: Because we're not.
>> Bianca Gandolfo: Better now?

[00:01:09]
>> Speaker 2: Yep.
>> Bianca Gandolfo: Okay. So here's our depth for search. So the first thing we're doing is catching if there's any errors. This is saying if the value doesn't exist in our adjacency list, we're gonna say it's invalid, or if the function that we're passing in is not a function.

[00:01:35] The idea here is that our depth for search. We're not just exploring it for no reason we're gonna be passing it a callback and doing some operation on each node.
>> Bianca Gandolfo: So whether it is adding exclamation points at the end, which we talked about when we were talking about trees.

[00:01:52] Or doing some real work, maybe you're going through and I don't know. For some reason, appending all this to the DOM so that you can see it and it's not just this abstract concept. Maybe for each node, you're going to pin some image with the value, and for each edge you're gonna paint a line between those two nodes.

[00:02:21] So you can show from our adjacent c list and turn it into a data visualization on the front end. That could be one reason. You can also do that with breath for research. There's no reason to only do that with that first search. Okay, so we're checking, great.

[00:02:43] And we're gonna track two things. Whether it's been visited and the distance. So this is how deep we go into the into the data structure and we're gonna pass it into our function everytime for the cases where the distance is important, cool? So, once we have done that once we have run the function on it we consider it visited and we set that flag to true in our visited object.

[00:03:18] So here we're just using an object as I called it the bread crumb method. Where we're just using it to see if we have, it's just a quick look up to see if we have looked at something before. And so if you just set it to true in this object you could just do a quick look up, just to see if it's been visited.

[00:03:40] Cool, make sense, great. So you could see is where we're doing that check. It's just one little line. If, neighbor has been visited then you just return. So, my, something. I was gonna swear but I stopped myself. Here is some chain stuff going on. We are looking through the nodes.

[00:04:09] This is our adjacency list, right. For each of those, we are going to run this function. At the end we are passing this. Which is gonna set our contacts, so we don't lose that this is our current,
>> Bianca Gandolfo: Node, yeah, okay. So if we visited it, we are done, we don't wanna visit things twice cuz then we could get stuck in loops.

[00:04:44] Otherwise we're gonna traverse, which is our recursive call.
>> Bianca Gandolfo: Cool, I'm gonna do our thing that we do with the stack, trace.