BFS Lab

The most difficult portion of this lab is understanding how the BFS algorithm works, so that is what we will be covering. The actual coding and implementation will be left up to you; after all, this is the final lab, and it’s high time we stopped babying you.

The Algorithm

The key point of the breadth-first search algorithm is the queue. If you used a stack, you’d get depth-first search instead. Imagine we had a graph such as the following:

Imagine we start at A. When we perform a BFS, the order of the nodes within the same level do not matter. So whether we choose to explore B or C first does not matter; however, we cannot explore F or G since those are two levels away.

So we start with level 0: A. First, we add it to the stack.

Then we pop our queue. This was fairly trivial, since only one thing was in our stack (at this level). We get back the same node, A. Now, we get a list of all of its neighbors.

Let’s imagine the list is in the following order: [B, D, E, C]. This is the order in which we’ll add to the stack. Our queue now has, in order, B, D, E, C. (B is first, so when we pop, that is the vertex we will receive.)

And that’s it! We’re done with A, so we continue to the next depth.

Now we move on to depth 1. Same thing here: we pop the stack.

We get a vertex, B. We get all of its neighbors: A, F, G. But wait! We already visited A right before this. So do we add it to the stack? Of course not. We need to maintain a dictionary of visited nodes to make sure we don’t visit the same node twice. Since A has been visited, we add F and G to the stack.

Our stack now looks like this: C, D, E, F, G.

We continue with depth 1. This time when we pop, we receive C. This node only has one neighbor – A – and it has already been visited! So nothing much to do here. Same thing with vertices D and E.

Now we are done with depth 1, so we can finish up with the final depth 2.

The process is fairly similar for each vertex:

* Pop the queue
* Mark the vertex as visited
* Get a list of all of the neighbors
* Add any neighbor that isn't already visited to the queue

And we keep going until the queue is empty! That’s it for BFS!