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 "Pseudocoding BFS" Lesson
[00:00:00]
>> Bianca Gandolfo: Let's pretend that this is an un directive graph. Yeah, let's pretend this is un directive graph, which means, in our adjacency table we need to use our imagination just a little bit and I'm sorry. You have to do this, this late in the day. But that means so, for example, three, four.
[00:00:19] Four also has a, Three in here.
>> Speaker 2: End of two?
>> Bianca Gandolfo: Well there will be twice as many edges, because with an undirected graph you represent both ways. So if there's, a connection between four and two, in four's adjacency list, you'll have two and in two's adjacency list you'll also have four.
[00:00:42] you just need to make sure you're doing both. And we can then ignore these arrows, and we can just focus on, traversing in the right order. Just like simplify our life. Okay. So we know we have to have a queue. Somewhere, somehow we need to queue in order by layer.
[00:01:06] True? Okay. Queue, some order by layer such that, the least deep nodes are processed first.
>> Bianca Gandolfo: Fair? That's the English version. We'll see what that actually looks like in code. So we have a queue. Somehow we need to, create that queue.
>> Bianca Gandolfo: How might we do that?
>> Speaker 2: You use the nodes in four's adjacency list
[00:01:58]
>> Bianca Gandolfo: Yeah absolutely. That wasn't so hard. So, so what was the question were answering? How do we find our first queue? Where could it be? How do we create it? We have that adjacency list right? So, we can imagine four and four's adjacency list. So we have four, we have an adjacency list.
[00:02:26] We have two, three, and five, something like that. So we really have the queue, here. Cuz a queue is just like an array. So either, we use the data structure that we have, in our adjacency list or you could push into in external queue. The specifics on how you wanna do that again, I'm not dogmatic about that.
[00:02:58] It's just, at the end of the day, we have a queue here. We need to make sure that, we go through it. Cool. Awesome, so we're good there. So we'll start with four, or the current node, which would be four.
>> Bianca Gandolfo: Process, profess, profess your love for our queues.
[00:03:24] Process the adjacency lists,
>> Bianca Gandolfo: For current Node.
>> Bianca Gandolfo: Does that make sense?
>> Speaker 3: So based on the direction, it's a little confusing when you have two, three, five and that [INAUDIBLE] because the arrows are pointing towards four, four from two and three and it's [INAUDIBLE]
>> Bianca Gandolfo: Yeah, so yeah, yeah, so let's just pretend that this is an undirected graph.
[00:03:59] Yeah, so just pretend it's an un-directive graph, just so we can make our life easier here and focus on less details. So that's why I made, a sample adjacency list for four,. If it was undirected, we would have all of the edges represented, versus the one that we have here, where it's only five because technically, in the directed graph.
[00:04:21] It only has one edge, directed to five, connected to five. But,
>> Bianca Gandolfo: I say, let's not clutter ourselves right now with directed graphs, and let's just focus on just the core concepts and then we can, we can make it complicated later, if we want. Okay, where were we?
[00:04:46] So, we're gonna process the adjacency list for our current Node, and then what happens next?
>> Bianca Gandolfo: So, this would basically work, if we just needed to process one layer, right?
>> Speaker 2: Right, then you have to go and process the layers following.
>> Bianca Gandolfo: Then process next layers. So the next layers would be, we need to get to six, and then we need to get to one.
[00:05:23] So that would be the next layer.
>> Speaker 2: Right, and then you would look at their adjacency lists and you wouldn't see any more that you haven't already seen. And so you would not process any more.
>> Bianca Gandolfo: Yeah, absolutely.
>> Bianca Gandolfo: But how do we do that?
>> Bianca Gandolfo: So, we need to make sure that we go through, our adjacency list first, right?
[00:05:55]
>> Bianca Gandolfo: And process it, because it needs to be in that order. That makes sense to me.
>> Speaker 4: You want the adjacency list for the nodes in the adjacency list?
>> Bianca Gandolfo: Mm hm, yeah, so maybe the next step is, so we processed each one of those nodes. And then maybe as we're processing it, we can somehow, I don't know.
[00:06:26] Do something so that we have, something next to go to. Am I making sense? Is the objective clear? So we process a queue, or you know, process the array and then, and the question is then what? Miranda says, okay, why don't we process it again and then go and visit everything.
[00:06:52] Does that seem like it'll work? Okay. Process the next layers by looping through and then like going into those, right?
>> Bianca Gandolfo: I don't know, I have amnesia.
>> Speaker 2: But if it's a-
>> Bianca Gandolfo: So, we loop through. Here and we mark these as, maybe, visited, or whatever.
>> Bianca Gandolfo: Something like that.
[00:07:51] Or we put exclamation points at the end, very useful operation to do. So we did that, and then, we're gonna go again and we're gonna like, do what? Like look maybe in the adjacency list for, for it?
>> Speaker 4: Edges?
>> Bianca Gandolfo: Yeah. So we look through again, and then like, maybe, maybe just, what do you think about just like recursing?
[00:08:30] Here. Recurse with like, Gone.
>> Bianca Gandolfo: Does that make sense? So, we go to the next thing and the adjacency list, so lets just say two, so we look up (nodes[2]). All right, similar like we had this thing before, this underscore nodes. So we recurse, so we loop and then we recurse.
[00:09:02] And then we start over again.
>> Bianca Gandolfo: That seem useful?
>> Bianca Gandolfo: Do we have to do that?
>> Bianca Gandolfo: I think we're left with some questions to ponder.
>> Bianca Gandolfo: So the question is, how do we get to the next layer?
>> Bianca Gandolfo: How do we get to the next layer?
>> Bianca Gandolfo: Do we need to recurse?
[00:09:35]
>> Speaker 2: I feel like we might not need to.
>> Speaker 2: Because-
>> Bianca Gandolfo: You feel in your heart.
>> Speaker 2: Yeah, because we have the data structure that we can index into. It isn't like a linked list or a tree where you have to have the node to access the next one.
[00:09:53] You have all the information all the time, wherever you are.
>> Bianca Gandolfo: Well, that's true. But do you have all the information that you need. That's the question that we're gonna be left with, cuz' we're running out of time.
>> Speaker 2: Right. We're gonna ponder.
>> Bianca Gandolfo: We're gonna sleep on it.
[00:10:08] We're gonna come back and we're gonna have all the answers to all the questions, maybe. So wait, so how do we get to the next layer? Do we need to recurse? Yeah. What about that flagging stuff, we've been talking about that? When does flagging happen? Do we even need to recurse?
[00:10:30] If we don't, how do we do it and the whole point, if we wanna get to that next layer.
>> Bianca Gandolfo: Seem fair? Cool. So these are things that you're gonna explore when you're implementing your code. It's gonna be easier for you to debug, while you're actually coding it out.
[00:10:53] Careful for loops, infinite loops. Great.
>> Bianca Gandolfo: So, you can check back tomorrow morning. We'll go through, the answers to these questions. I don't expect you to do these on a Friday night. But if you happen to get a chance, it will help you, while we're exploring the solution tomorrow, come with good questions and deepen your understanding.
[00:11:29] So we'll do that and we'll do some like recapping. Sound fair? Sound good? And then we'll jump right into hash tables and we're gonna be out after lunch. I may do a summation right after lunch. About, okay, so you have these foundational pieces like I've been saying. And, we're starting to piece them together.
[00:11:52] We're using a queue, we're talking about maybe using hash tables, and we've used other pieces. Now we have, we know how to do breadth first search for our trees, or we will once we figure it out tonight and tomorrow morning.
>> Bianca Gandolfo: So, it's all sort of coming together.
[00:12:12] And then, there's a whole new layer, right? That we take these foundational skills and apply to even more problems, like real world problems. That are maybe important to you, maybe important to your interviewer.
>> Bianca Gandolfo: So that's what we'll do tomorrow. We probably won't go in depth into how to implement them.
[00:12:34] It'll be more like, okay you know these things, you can implement this now. You know these things, you can implement this now with these pieces. Kinda thing, and then it'll be up to you to go on and explore that on your own.