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!