Data Structures and Algorithms in JavaScript

This course has been updated into a 4 part series! We now recommend you take the A Practical Guide to Algorithms with JavaScript course.

Check out a free preview of the full Data Structures and Algorithms in JavaScript course:
The "Breadth-First Search 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 shifts back to the breadth-first search algorithm and walks through the solution to the Graph implementation of breadth-first search. The code for the solution is located on the "solutions" branch in the Github exercise repository.

Get Unlimited Access Now

Transcript from the "Breadth-First Search Solution" Lesson

[00:00:00]
>> Bianca Gandolfo: Breadth-first search follows this pattern where we traverse our graph in layers rather than all the way down first and then the next ones. So just so we can trace it here, it's going to go by level, etc. So
>> Bianca Gandolfo: If we were to console log the depth every time that we do this traversal, it would log something like this.

[00:00:32] Zero, one, one, one, two, two, two, two, three.
>> Bianca Gandolfo: So we're going by depth.
>> Bianca Gandolfo: We're good?
>> Bianca Gandolfo: Cool. And we talked about how depth-first search uses a stack. We're using a stack under the hood with recursion. However, breath-first search, we have to explicitly use a queue to make it work.

[00:01:02] So, we're going to use a cue for our stack and when you're thinking about depth first search versus breath first search. The first thing that should come to your mind cue for BFS, stack for DFS, that should be the first thing that comes to your mind.
>> Bianca Gandolfo: Cool.

[00:01:29]
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: What else do I wanna tell you about it? Okay, okay.
>> Bianca Gandolfo: Should we just jump in? Explore the code, and then we'll. We'll explore the code and then we'll use our example again, okay? So, we're gonna do a check if it's valid. Again, we have this visited object, and then we have the queue.

[00:01:58] So the queue is just gonna add our value, and then make it's gonna make it an array. So we are going to give it a 0 if it's visited in this case, and then we're gonna see. So while the queue has something in it, we're gonna do this loop,

[00:02:22]
>> Bianca Gandolfo: Cool? All right. So, for our first no were going to shift our queue. What does shift do? Anyone know? Let's check it out.
>> Speaker 2: Move everything over one.
>> Bianca Gandolfo: Mm hm So if we have q and it's an object, I'm sorry it's an array, and we say q shift and then we look at q it's gonna take off the first one and shift everything over by one.

[00:03:05]
>> Bianca Gandolfo: We're good? Great.
>> Bianca Gandolfo: Okay, so that's what we're doing here.
>> Bianca Gandolfo: Then we're running our function. We're going to pass our node And then visited node, interesting.
>> Bianca Gandolfo: Let's keep that in our mind. Why might we pass that? Very strange. So we have our neighbors.
>> Bianca Gandolfo: We're gonna be filtering.

[00:03:41] So what does filter do? Anyone know, anyone familiar with the interface of filter? No? Some of us? So, filter is going to loop through all of the elements in a collection and if it returns true it's going to return an array of all of those values that were true, based on some function that you passed in.

[00:04:21] So here's our function that we're passing. Here. So, as you can see, there's a certain, something has to be met in order for it to return true. If that condition is met then we're gonna add it to our neighbor's array.
>> Bianca Gandolfo: Any question about what that's doing? What condition needs to be met?

[00:05:01]
>> Speaker 3: It can't be visited.
>> Bianca Gandolfo: Yeah, mm-hm, yeah. So if,
>> Bianca Gandolfo: If we do a look up on our visited object and it's undefined, we're gonna enter in here. So we're gonna call it visited[neighbor], visited[node]+1, we're adding one here and then we're gonna return true. So essentially, we can't have visited it.

[00:05:36] So this is a way for us to build a queue based on the nodes that we haven't yet visited and by queue, I mean an array. Cool.
>> Bianca Gandolfo: So there we are, and then we're gonna do this thing. QUEUE = queue.concat(neighbors). Let's see what that does. Where's our queue?

[00:06:04] Here's our queue. And then we're gonna say neighbors, neighbors, and let's do like this. So we say q.concat(neighbors), right? We pass it neighbors. Does anyone know what this does? If I hit enter what's gonna happen?
>> Speaker 3: Turn that into a string [CROSSTALK].
>> Bianca Gandolfo: Tacking it on the in.

[00:06:33] Concat immediately you see concat with strings. But here we are just concatenating two arrays. We're just gonna put it on the in.
>> Bianca Gandolfo: Cool. All right. So, here we are. Adding all the neighbors next on the queue. Okay? And we're going to keep doing that until our queue is empty.