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:
- Dequeue from the front, and set its color to black. (We maintain the invariant that all vertices in the queue are gray.)
- For each neighbor of that is colored white, we set it to gray and put into queue.
- Set the parent of to and set the level of to .