## 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. $s$ is initially gray.

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

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 ${s}$. While the queue is non-empty, we:

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