Breadth First Search Solution

[00:00:00]
>> Bianca Gandolfo: So let's walk through this solution. So we have our BFS, we start with any node. Again, let's just start with one for consistency and we'll see how this is different. Cool, so we're going to push our starting node into the queue, and we're gonna mark it as visited.

[00:00:22]
So queue does have a length, we are going to shift, which means we're going to remove the beginning of the queue.
>> Bianca Gandolfo: And then we are going to add all of the neighbors, all of these people,
>> Bianca Gandolfo: To,
>> Bianca Gandolfo: Our queue, okay. And then we're gonna do work, right?

[00:00:51]
So in this case, we've come to log in, it's gonna,
>> Bianca Gandolfo: Look like that, and then for each neighbor,
>> Bianca Gandolfo: For the neighbors, each neighbor, if it's not visited, we're gonna push it. So we did that already here, and we're gonna mark it as visited. So we're gonna add two and five to our visited list.

[00:01:21]
And we're gonna start over again, so we're gonna take off the two from our queue. We are going to capture all the neighbors, there's a lot. And we're gonna do work.
>> Bianca Gandolfo: Actually, it's gonna log like this. We're gonna do some work, in this case console log and then, for each of our neighbor that's unvisited.

[00:01:47]
So, one is visited to get that, five is visited skip that three is not visited. So we're going to push three, and we're going to mark it as visited. And we're gonna go back up to the top. We're going to remove the next one,
>> Bianca Gandolfo: And grab all of its neighbors, there are all of its neighbors, we're gonna do some work.

[00:02:29]
>> Bianca Gandolfo: And for each of the it's neighbors, if it's not visited, so we're looking at five. Four is not visited so we're gonna add it to the queue. One is visited, two is visited, all right? So queue that link, and we're gonna take the next one which is three.

[00:02:48]
And we're gonna do some work, and for each of its neighbors two and four that aren't visited, that's two visited, no. We forgot to add four.
>> Bianca Gandolfo: Okay, so,
>> Bianca Gandolfo: We did three, so two and four are visited. So we don't do anything, and then we pop off four.

[00:03:16]
We do some work, does it have any unvisited? Nope.
>> Bianca Gandolfo: And that's it, so the way that this prints out, it goes one, and then the first layer is these two adjacent, right. And then, it goes to two after and visits its adjacents. And then after that, this is a pretty small graph, then we just return.

[00:03:47]
So when you see how it goes layer by layer, versus the other one would go through all of an entire unvisited path before returning up. Again, this is an editor approach, you can also easily do this for. Actually no, you can't, cuz it's a queue. Well, okay, you can, it is not recommended, it is not recommended.

[00:04:16]
Okay,
>> Bianca Gandolfo: Great, let's talk about time complexity with the code open. So, because we are implementing this with an array, it's a little bit different because we are shifting. Remember shifting is linear, is it different? No, I think it's fine actually. Well, so we are shifting inside of a loop, and that should throw some red flags, right?

[00:04:43]
If you're shifting inside of a loop, that's starting to look a little bit like N squared, so keep that in mind. However, you probably wanna implement this with a link list, so that you don't have to shift. You can just remove from the front, in constant time and call it a day.

[00:05:03]
And this would just be linear because we'd only be worrying about the work of this while loop. Everything else is not a big deal, especially here because even though it is looping. Through all the neighbors, it's not really doing much work. Cuz it's not really getting into if the neighbor is unvisited.

[00:05:28]
So, I would say that that's fine, I would say linear.