for S

Graph traversal, or the process of moving around a graph, is one of the most fundamental problems in computer science. One way of doing it is with Breadth First Search.

Let’s say you had a graph of some sort - a network of cities. Each city is just hanging out, doing its thing, but one day you hear that a diamond necklace was stolen from your city, and the thief was spotted in one of the other cities. You don’t know which of the other cities - mostly because you are a civilian and the cops don’t see why you should know. For various reasons, you are not allowed to contact anybody, and must travel yourself in order to check for the presence of the necklace in a given city with your DiaDetector®, which has a range of 20 miles.

You live in an absurdly large country of the future, with a large number of cities. Here’s a network depicting all the cities:

no label network

You want to answer 2 questions:

  1. what is the shortest path from your city to the city with the stolen diamond necklace?
  2. where is the stolen diamond necklace?

Each city is around 20 miles in diameter, so all you need to do to ascertain the presence of the diamond necklace is get to the center of the city and fire up the DiaDetector®. You want to make sure you don’t forget going to a city. You also want to be able to keep track of the path from your city to a given city (you don’t have access to this overall map).

According to the excellent Khan Academy page on Breadth First Search, the process assigns two values to every single node in a graph:

  1. A distance, giving the minimum number of edges in any path from the source vertex to vertex v.
  2. The predecessor vertex of v along some shortest path from the source vertex. The source vertex’s predecessor is some special value, such as null, indicating that it has no predecessor.

Here is a good Stackoverflow thread that details the differences between Depth First Search and Breadth First Search. Depth First Search is another paradigm for approaching this.

Assuming you did the background reading, and assuming I did an okay job of explaining it, you now see one method of traversing the graph of cities in your country:

labeled network