Scaffolding

Each vertex remembers its own color: white, gray, black. All values are originally white. Keeps track of which vertices are discovered/in the progress of. is initially gray.

Track the “level” of each vertex. At the end, this will be equal to the shortest distance to . Initially set to except for itself, which is just .

For each node, keep track of the parent node that discovered it. This allows us to build a tree.

Algorithm

Maintain a queue, initially set to just . While the queue is non-empty, we:

  1. Dequeue from the front, and set its color to black. (We maintain the invariant that all vertices in the queue are gray.)
  2. For each neighbor of that is colored white, we set it to gray and put into queue.
  3. Set the parent of to and set the level of to .