This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.
Transcript from the "Graph Traversing & Depth-First Search" Lesson
[00:00:00]
>> Bianca Gandolfo: What do we know about depth-first search? It's the most awesome search.
>> Speaker 2: It's my favorite, certainly, but it's where you search through everything and you go down first.
>> Bianca Gandolfo: Yeah, yeah. Exactly, so you go all the way down, down, down, into the depths. And then, you go up, up, up, and then to the side.
[00:00:24]
>> Bianca Gandolfo: And I think I have, here we go. It probably makes more sense than my description. All right, so we call this graph traversing. Here is an example of depth-first search, so we go all the way down to the bottom, and then we come up, and then we go to the other side.
[00:00:48] So why, we can find paths, cycles, connectivity and more. This is like, I don't know, this is where the magic is, with paths and cycles for graphs. Lots of cool stuff that you can do with that. Once you really master these fundamentals that we're going over in this first couple days, it's gonna arm you with a lot of tools to apply to some more advanced algorithms that can really open up some cool stuff.
[00:01:15] For your life, I don't know if you're into that. For your whole life will be changed forever. [LAUGH] I might be exaggerating a little bit, but. Or not, or maybe I'm not, I don't know, maybe it gets you a really good job.
>> Speaker 3: Maybe you're underselling it.
>> Bianca Gandolfo: Yeah, it's probably what I'm doing.
[00:01:35] Cool, so one thing that I want to talk about is this explored, visited, undiscovered concept that we didn't really talk about in trees as much. And this is one way that people describe and represent in code whether we need to keep exploring down a path, right? Because in a tree, there's a natural termination, right?
[00:02:05] And that's not necessarily true with a graph, because they're cycles. And so we have to flag if something has been explored. Meaning that you have looked at all of the adjacent nodes, or if it's visited, right? So once we go from A to B, B is now visited, A is visited but not explored, because we haven't explored all of its adjacent,
[00:02:35]
>> Bianca Gandolfo: Nodes, vertices, nodes, vertices.
>> Bianca Gandolfo: Cool, undiscovered means that we haven't gotten there yet.
>> Bianca Gandolfo: And so you can use these flags in your code to help keep track on where you are
>> Bianca Gandolfo: Or you can just use one or two of them, you don't have to use all three with some, it depends on which solution you look at.