#### Real world examples

Graphs can be translated into real-world events with connections to computer science and without connections to computer science.

- Web crawling requires graphs and often times breadth-first searches.
- Social networks use graphs and graph traversal to map friends or connections.
- Garbage collection in higher level programming languages is often times done using graph traversal.
- Anything that resembles a viral growth pattern can be modeled using graph traversal (patient zero infecting other 'nodes' with a common edge).
- Finally, since breadth-first searches are trying to find the shortest route between two positions, GPS navigation often uses it in finding routes.

#### Can't go it alone

In order to properly implement breadth-first search (BFS) we are going to need to utilize another common data structure, the queue. As a very brief overview, a queue is a First-In-First-Out (FIFO) data structure. This means that the first object that is enqueued into the tail-end of the queue will be the first one dequeued off the head. It's easy to imagine a queue as well... a queue for the grocery, first in line is first checked out.

#### The build-up

Here is our original graph,

As we mentioned before *V = {0, 1, 2, 3, 4, 5, 6, 7}* and is our set of vertices. Our set of edges will look like *E = {[0, 1], [0,4], [1, 5], [4, 2], [4, 5], [5, 2], [5, 6], [2, 3], [3, 6]}*.

To each of vertices we are going to add two properties, distance from the origin and predecessor. If we were looking at this from an object-sense all of these would be key-value pairs within a vertex object.

- Distance will tell us how many steps that vertex is away from the origin.
- Predecessor will tell us where that vertex came from.

The entire point of a BFS is that we search for and find everything that is *x* distance away from the origin before ever reaching any vertex that is *x + 1* distance away.

#### The good stuff

I'm going to walk through a BFS for the graph we already have step-by-step and by the end we will have a basis for implenting an algorithm! Let's start at 0.

- Enqueue the 0 vertex, which has a
*null*predecessor and 0 distance. - Dequeue 0, and enqueue both 1 and 4, in that order. Each with a predecessor of 0 and distance of 1.
- Dequeue 1, and enqueue 5 which has a predecessor of 1 and distance of 2.
- Dequeue 4, and enqueue 2 which has a predecessor of 4 and distance of 2. Notice we skipped 5 because we already enqueued it. Now we have a queue with 5 and 2.
- Dequeue 5 and 2, and enqueue 3 and 6, with predecessors 2 and 5 and distance of 3.
- Finally we dequeue 3 and 6, no other vertices to enqueue and thus the BFS is terminated.

This is our graph post-traversal with distance, predecessor filled in, in that order.

That was a very brief overview of BFS, there's one more installment coming where we'll go more in depth into the details of the algorithm and maybe even throw down a Javascript implementation. Thanks and leave a comment!