Data Structures and Algorithms in JavaScript

# Pseudocoding DFS Part 2

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Pseudocoding DFS 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 pseudocoding the depth-first search algorithm. The base-case occurs when there is no longer any where to explore. Until the base-case is reached, the algorithm recursively loops through the edges. As nodes are explored, they must be flagged or marked as visited.

Get Unlimited Access Now

Transcript from the "Pseudocoding DFS Part 2" Lesson

[00:00:00]
>> Bianca Gandolfo: Can we break the pseudocode down more?
>> Speaker 2: So are you setting flags on the nodes?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 2: Okay?
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Okay, or like a flag?
>> Bianca Gandolfo: Yeah, so that way when you're checking, you can see.
>> Speaker 2: Right.
>> Bianca Gandolfo: If you've been there or not, yeah.

[00:00:22]
>> Bianca Gandolfo: And we don't really need to do that with a tree, right, because we don't have to worry about cycles. Right.
>> Bianca Gandolfo: Okay.
>> Bianca Gandolfo: Does anyone have a solid pseudocode solution?
>> Bianca Gandolfo: Okay, so each node needs to be visited and explored.
>> Bianca Gandolfo: So we'll visit,
>> Bianca Gandolfo: Does that seem fair?

[00:01:17] Like we have to go to each node, we have to visit it and then we have to make sure that we have visited everything around it and marked as explored before we just said that we are done.
>> Bianca Gandolfo: Cool, and then it recurse, we have a base case, which is what?

[00:01:38]
>> Speaker 2: If it's been explored.
>> Bianca Gandolfo: Yes, if it has been explored which we know that how?
>> Speaker 2: Because there's going to be an attribute on that node that tells us it's been explored or not.
>> Bianca Gandolfo: Or there's like no further places to go.
>> Speaker 2: Or there's no further place to go, yeah.

[00:02:02]
>> Bianca Gandolfo: Yeah, so what does that mean? So know where to go, it could mean that for example for the 6, there's no adjacency list, or it's empty. So an empty list or it could be what else? What are some other examples?
>> Bianca Gandolfo: So it's either visited or explored already, cuz you don't wanna go there

[00:02:34]
>> Bianca Gandolfo: You don't wanna recourse into something that is already being visited or explored.
>> Bianca Gandolfo: Two way two kind of based cases scenario, okay? So that every time we visit.
>> Bianca Gandolfo: If we call this our recourse and we call this traverse, right.
>> Bianca Gandolfo: Another thing we know about recourse is we have to break our problem down into smaller pieces, right.

[00:03:08] So what pieces?
>> Bianca Gandolfo: What pieces do we want to break it down into.
>> Bianca Gandolfo: All right, we have our nodes
>> Bianca Gandolfo: So we're saying each node needs to be visited and to marked as explored, is that the same thing?
>> Speaker 3: Does, like do you mark a node as explored once it's been visited or is there a little more to it?

[00:03:46]
>> Bianca Gandolfo: There's a little more to it, so visited happens. So for example, we visit 1 and then we go all the way down, all the way down, all the way down, all the way down to 6, and 6 is the first one we mark as explored.
>> Speaker 3: Okay, cuz there's nowhere else to go.

[00:04:00]
>> Bianca Gandolfo: There's nowhere else to go. And then, because of that, 5 has been explored, 4 has been explored, 2 has been explored, 1 is still visited 3, we visit. We check, we don't have anywhere to go and now 3 is explored. And now we pop back, 1 is explored.

[00:04:18] Okay?
>> Speaker 3: So when we first go to a node we need to check if there's anywhere else we can go, yep.
>> Bianca Gandolfo: [COUGH] So is there somewhere to go or is everything in the adjacency list been visited slash explored. Maybe we just want to say explored. I don't know.

[00:04:48] I haven't committed.
>> Speaker 3: Okay.
>> Bianca Gandolfo: To either one.
>> Speaker 3: So with your definition 6 can't be explored, right? 6 can't be visited.
>> Bianca Gandolfo: So 6 is explored, 6 is actually the first one that we consider explored Because as we go down, we start here, we go down, we do gown, and we go down and we get to 6.

[00:05:10] At this point, 1, 2, 4, and 5 have all been visited, but we have not marked them explored yet. Because we're not sure yet that there's no more other adjacent vertices, right? Because we haven't checked, we've only gone down one path. All the way down to the bottom.

[00:05:29] And we wanna make sure that we account for other path, so that one is just visited because we go down this way. We hadn't yet explored the 3 and so, explore is when all the edges and vertices are done. So basically, explore is when we've gone to both of the items at JSON C list.

[00:05:58]
>> Bianca Gandolfo: So we need to traverse somewhere in our adjacent C list, right? We have two options of what we can traverse. We can traverse either the edges or we can traverse through the nodes themselves, right. Because that's what we have, we have either an array of our edges or we have these values in our object, right.

[00:06:27] 1 to 6, yes. Mm-hm.
>> Speaker 3: But the edges are what represent, but places we can go.
>> Bianca Gandolfo: Yeah, so what does that tell you?
>> Speaker 3: That that's what we wanna traverse.
>> Bianca Gandolfo: Yeah, so we wanna traverse into the edges.
>> Speaker 3: Yes.
>> Bianca Gandolfo: So the first time we do this.

[00:06:49] Right, this that knows that value, we're looking at one.
>> Bianca Gandolfo: And we wanna go into the first item, two.
>> Bianca Gandolfo: And then, let's just say we recurse. We recurse, so we visit.
>> Bianca Gandolfo: We visit 2, which is here, and we can go to 0, right? So if we wrote this code just looking at the first index.

[00:07:27] It would kind of work for a while, right, we go to 4, 4 goes to 5, 5 goes to 6, 6 meets our best case, so we jump out. We jump out, we jump out, we jump out, we jump out. The time it doesn't work is when our adjacency list is greater than size 1.

[00:07:49]
>> Bianca Gandolfo: Do you see why?
>> Speaker 3: Because we're just, we want to go to the first one?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Could we use a loop there to traverse all of them?
>> Bianca Gandolfo: Mm-hm.
>> Bianca Gandolfo: Let's call it array of edges
>> Bianca Gandolfo: No, what did I hit? God, it scared me.

[00:08:35] I was like don't erase everything, okay?
>> Bianca Gandolfo: Okay, so for i we're gonna loop.
>> Bianca Gandolfo: How does that land with us?
>> Speaker 3: [INAUDIBLE] Mm-hm.
>> Bianca Gandolfo: So we'll start with 1, is 1 visited or explored, or in empty list? No, so we're gonna loop through it. So the very first one we're gonna traverse- Yep.

[00:09:27] Which is gonna be our recurse of call.
>> Speaker 3: Yeah. Go to 2, is 4 explored or visited?
>> Bianca Gandolfo: No, so we will traverse. Same thing, we will traverse, we will traverse, we get to 6. 6 is now, has an empty list, so we return, 5. So, again we're not flagging here so there at some point we're gonna want to flag, but let's pretend that we did.

[00:09:58] So 6 s explored at that point and then we go up, up up up, to 1. And in this 1 we're back at this 4 loop, then I will be 1, and then that's when we go to 3
>> Bianca Gandolfo: So, who wants to teach me about how this code works.

[00:10:41]
>> Bianca Gandolfo: Anyone?
>> Bianca Gandolfo: Well, everyone all the same time.
>> Speaker 3: Anyone interrupt this 1.
>> Bianca Gandolfo: [LAUGH] [LAUGH] Let's see, could just take a guess. So the way you learn is trying it and then maybe it was wrong and then I'd tell you the right way and then suddenly you'd know where your mistake was in your thinking.

[00:11:08] So by taking a stab at it and showing us your mental model it's going to help you and it's also going to help probably the other half of the class who also has this mental model that may be incorrect. Or, you got it 100%.
>> Speaker 3: And then you get all the glory.

[00:11:27]
>> Bianca Gandolfo: Yeah, and then you just get credit for that.
>> Bianca Gandolfo: Anyone, anyone?
>> Speaker 3: I'll give it a go if nobody wants to.
>> Bianca Gandolfo: Okay.
>> Speaker 3: I feel like I'm hogging all the interaction chances though.
>> Bianca Gandolfo: Well.
>> Speaker 3: So we'll start off at 1, and so we'll check there if it's an empty list, or if it's already been marked, visited, or explored.

[00:11:57] None of those things are true, so we move through and loop through its array of edges. We go through the first entry in that array and that's 2. We do a recursive call to our traverse on 2. We check if 2, either contains an empty list or has already been marked visited or explored.

[00:12:17] That's not true, so we move down to our second thing, and we loop through its array of edges. Its array of edges only contains 4, with triggers on 4. We check if it has an empty list or if it's been visited or explored. That's not true, so we loop through its edges.

[00:12:36] So we'd go into 5,
>> Speaker 3: It does not have empty lists or has been visited or explored. So we'd traverse on 5, which gets us to 6. Now 6 has an empty list, so we return and don't go anything further. Which pops us back into,
>> Speaker 3: 5, so we'll finish that loop.

[00:13:03] There's nothing else in the loop, so that pops us back to 4. We'll finish that loop. There's nothing else there, so that takes us back to 2. Finish that loop, nothing else there, that takes us back to 1. Now there is another entry in that loop, so we'll go into 3.

[00:13:18] And then from 3, we'll check if it's got nowhere to go, which is not true, or if it's been visited, which is not true. So we'll traverse 3, we'll loop through its array of edges, which takes us to 4. We go to 4, now it's already been visited so we return back to 3.

[00:13:37] And there is nothing else to go in to that loop. We go back to 1, then we are done, right? Because, that loop is finished.
>> Bianca Gandolfo: Yup, perfect. Snaps that was beautiful. Lets give him snaps. Don't need to be stingy with your snaps. They don't cost that much.

[00:13:57] [LAUGH] All right, okay, cool. So before, we're not gonna do exercises, we're just gonna jump into Breadth-First Search. So you have some to dos here, to do, where do you put flags?
>> Bianca Gandolfo: How many flags do we need? Do we need explored and visited?
>> Speaker 2: No.
>> Bianca Gandolfo: Visited or just one, doesn't matter, you can decide.

[00:14:27] What are the questions that are open? I think those are our main open questions it's just around the flagging.