Breadth First Search

[00:00:00]
>> Bianca Gandolfo: On to the next, breadth first. So breadth first is another traversal strategy where we go layer by layer. And like I mentioned before, the difference between breadth first and depth first is that breadth first is gonna use a queue versus a stack. So let's take a look.

[00:00:24]
So first of all i wanna like just take a step back and talk about why this looks a tree when it's really a graph. And it all has to do with like for these searches, you start with one node and it's kind of like a root node, so I kind of think of this graph if kind of think about it if you pick it up.

[00:00:42]
And it hangs down, they kinda look like a tree, right? So we need to reverse a graph and breath first or depth first it kinda make a tree, or does make a tree. So you could represent a graph as a tree through reversing it and setting up the edges as you traverse it.

[00:01:07]
>> Speaker 2: Why the two pictures? I mean, they're the same thing?
>> Bianca Gandolfo: Yeah, it's just the idea, doesn't it look more like a tree on the one with the curved lines?
>> Speaker 2: Yeah, okay, I see what you're saying, okay.
>> Bianca Gandolfo: Yeah, so if you see, we're starting with S and if you're also having trouble thinking about what are these levels like a tree?

[00:01:30]
If you just pull it up like this you will see how it falls into levels. You know what it mean? So other people talk about it like spiraling out, spiral, spiral. I kinda think about it like this, like a string, pull it up. Cool, all right, so here is our pseudo code for breadth first search.

[00:01:58]
So the first thing you wanna do, start with the vertex and you mark it as visited, right? Again we have an object, store some things, say that it's visited. Then we add it to our queue, while the queue is not empty, you are going to traverse each edge and for each edge incident to vertex.

[00:02:20]
So, for breadth first search you take the steps of, you add the current node to the queue, then you dequeue it to process it. And you add all of its children to the queue, and then you dequeue the next one, add all of its children to the queue.

[00:02:54]
>> Bianca Gandolfo: Dequeue it, add all of its children to the queue, etc, etc. So for S, so we enqueue it, here we are, it's in the queue. We dequeue it, which means we've visited it. And then we add all of the children, all of its adjacent vertices and then,

[00:03:22]
>> Bianca Gandolfo: We dequeue that. Add all of its adjacent vertices that are unvisited, that's important then we dequeue it. C, add all of its unvisited adjacent vertices, which is none. And then you keep going down and down and down until it's empty. This is, [LAUGH] some in-depth pseudo code to help you with the exercise.

[00:03:47]
So feel free to reference this as you're going through it to walk you through, step-by-step, how do you implement breadth-first search.