Data Structures and Algorithms in JavaScript

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Breadth-First Search Stack Trace" 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 uses the traverseBreadthFirst() algorithm to traverse through a graph. She traces each iteration through the queue to reinforce the differences between depth-first and breadth-first traversal.

Get Unlimited Access Now

Transcript from the "Breadth-First Search Stack Trace" Lesson

[00:00:00]
>> Bianca Gandolfo: Ready to deep dive into our Breadth-First Search. I'm just gonna construct what our graph looks like at this point.
>> Bianca Gandolfo: So I'm just building our graph. For each node, I'm building a list of all of its neighbors. So for A, we have B, C, and D. For B, we have E, and F, right?

[00:00:32] For E, we have I. For F, we have an empty array, cool.
>> Bianca Gandolfo: Now, we're doing breadth search through the whole thing.
>> Bianca Gandolfo: Okay, for C, I can't actually, is C connected?
>> Bianca Gandolfo: Let's go with yes, let's just put a cycle on there because why not? So we have D and then we have G.

[00:01:11]
>> Bianca Gandolfo: Let me know if I'm missing anything. Then we have D, then we have G,
>> Bianca Gandolfo: And H.
>> Bianca Gandolfo: And what else? And then we have G, which has D and C. I forgot to do the background. Let's do this undirected, dang it.
>> Bianca Gandolfo: So if it's undirected, they each will have reference to everything that it's connected to.

[00:01:57]
>> Bianca Gandolfo: Let's see.
>> Bianca Gandolfo: Let me know where I need to add stuff, C, A, D, G.
>> Bianca Gandolfo: D, G, C, H C, A,
>> Bianca Gandolfo: My goodness. G, D, C, okay. Are we good? Do we have all of the things that we need in our list? So A, B, C, D.

[00:02:29] B, E, F, A, yep, B, F, A, E, we should have I, B and not F, not F.
>> Bianca Gandolfo: It's not connected to F, we should have B, C, should have D, G. And A, D, G, C, H, A, G, D, and C.
>> Speaker 2: You're missing I.
>> Bianca Gandolfo: Thank you.

[00:03:08]
>> Bianca Gandolfo: Okay, anything else?
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, so here we go. Here we go.
>> Bianca Gandolfo: I'm gonna take this out cuz we're just gonna assume that we're passing at the right thing.
>> Bianca Gandolfo: All right, so the first thing that we want to pass it is A, so we'll just say,

[00:03:44]
>> Bianca Gandolfo: myGraph, right, this is myGraph = adjacency lists, yeah? And then we're gonna say myGraph.traverseBreadthfirst, and we're gonna pass at A and then some function, right? Whatever function we want. Cool, so that's how we get started. And we're just gonna trace it all the way through. All right, so visited.

[00:04:17]
>> Speaker 3: I have a question.
>> Bianca Gandolfo: Sure.
>> Speaker 3: The reason that you didn't have the elements in the RA when you created the graph. Starting from levels, zero, one, two, like that. Is it because you're introducing your first element as saying later on?
>> Bianca Gandolfo: What do you mean?
>> Speaker 3: Like if you go to C, is D, G, and A.

[00:04:41] So why didn't you have A, D, and G plus C?
>> Bianca Gandolfo: You're asking like why is that array in a random order and not in the correct order? It has to do with when you add the edge. So whenever you add the edge you're gonna push the reference to the element into that list.

[00:05:11] First, maybe we added the edge T, E and then we added F, and then later we added A, so it is dynamic. Yeah, okay, here we go. So visited is empty. Q is gonna be value around the A.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: So now we're adding it to our array, our objects,

[00:05:49]
>> Bianca Gandolfo: Giving it the value 0, okay? So while queue.length so we have queue of length what?
>> Speaker 2: 1.
>> Bianca Gandolfo: We're gonna shift the node. So our queue is now empty, and then we pop off our A. So notice now A, we're going to pass it. We're also going to pass its number, which is zero.

[00:06:18] We have our neighbors that we're going to create right now. So we're going to say this.node. Probably this is better to say, you know what this means, right? This is going to be A, myGraph A. Does that make sense? I just called this something different. And then we're going to filter through.

[00:06:43] Loop through all of our elements in that array, so we have this array that we're gonna be looping through. Let's see where do we wanna put it.
>> Bianca Gandolfo: This is the neighbors. This is what we are starting with is not necessarily what we are saving because we have to filter it first.

[00:07:14] But we'll start with this. So the first neighbor is going to be B, right? So if visited neighbor, all right, let's look at our neighbor or visited, where's our visited thing? Here it is, so we don't have B. So B is undefined, right, which means we haven't yet visited it.

[00:07:46] We're gonna save it here. So now, our visited object has our A in it with 0.
>> Bianca Gandolfo: And then we have our B with 1,
>> Bianca Gandolfo: Cool? And then we´re gonna return true, which is going to add it to our actual neighbor's array.
>> Bianca Gandolfo: Okay, for our first filter.

[00:08:24] Our second filter, we're gonna now check C. That's now been visited, we're gonna add it.
>> Bianca Gandolfo: Why is this 1 and not 2?
>> Speaker 3: Same level.
>> Bianca Gandolfo: Mm-hm, cuz we're looking at the current node.
>> Bianca Gandolfo: We're gonna return true. And so this is going to put C in there, excuse me, and then now we're gonna check D.

[00:08:58] D has not yet been discovered, but we're gonna add it to our visited list. D, still gonna be 1. I'm gonna return true and now here we go. We've done filtering through all of their neighbors of our current node, which is A. And it leaves us with an array of everything that returned true which is everything that wasn't discovered.

[00:09:30] And now, we are going to concat that with our queue. Our queue is actually empty, so we're going to be left with this.
>> Bianca Gandolfo: Cool?
>> Speaker 3: Why are we seeing nodes nodes? I don't see any variable.
>> Bianca Gandolfo: Why are we seeing nodes_nodes?
>> Speaker 3: Yeah-
>> Bianca Gandolfo: Are those to _nodes?

[00:10:04]
>> Speaker 3: No, there is no nodes variable here, so why is?
>> Bianca Gandolfo: Yeah, our node is whatever was the first element in our queue. And this _nodes is from the implementation of your graph. So you can save all of your nodes in an object called underscore nodes. But I simplified it for us and just did A.

[00:10:31] So we could just do it like that,
>> Bianca Gandolfo: To make it easier. Cool, okay, so we were just doing work in that one while loop. Now, we're going to come back inside because we still have some items in our queue, and we're gonna shift it again. Remember, this is what our queue looks like now.

[00:11:05]
>> Bianca Gandolfo: This is our queue, we're gonna unshift it. So we're just gonna take the first one off.
>> Bianca Gandolfo: And we're gonna return B. Cool, and we're gonna do all of that same work with B, which is we're going to look through. All of it neighbors, we are going to make sure that they haven't been checked yet.

[00:11:33] And if they haven't, we're gonna add it to our neighbors queue. We're gonna give it a number based on the number away. Far away is from the original value that we pass in, which was A.
>> Bianca Gandolfo: That make sense?
>> Bianca Gandolfo: Because we're gonna say visited node, the current node is B.

[00:12:06] B's value is 1, plus 1 is 2. And so we're just keeping track here at what level it is.
>> Bianca Gandolfo: Cool? And then we'll keep doing that until we have explored the instructor. What's up?
>> Speaker 3: What will it be if we reach to A? Because B is-
>> Bianca Gandolfo: Yeah, yeah, that is a good question.

[00:12:34] So what if we look at A? A is a neighbor. But what is going to happen is that A has already been visited, so we won't go there.
>> Bianca Gandolfo: So first, we start off with a queue of A, then we add to the queue, all of the neighbors of B, or of A.

[00:12:59] So we have a queue of B, C and D. A has since been popped off once we entered into this layer. First, we go to B and we explore its children. We're gonna push this to the back of our queue over here ,which has the C and D at this point.

[00:13:17] Then we go to C, we explore it's neighbors. It is gonna look like a D, but we already have it in our queue. And so we're gonna keep going, like that. And we're concatenate that, then concatenate that. And then once we get to E, we'll check here. That one hasn't been visited, and then we'll concatenate to the back of the queue.

[00:13:41] And so we'll process our queue in order. And that's how we'll make sure that we're visiting all of the nodes that have not yet been visited in order by layer.
>> Bianca Gandolfo: And that is breadth-first search.