Breadth-first search

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 $\infty$ 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:

1. Dequeue $v$ 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 $u$ of $v$ that is colored white, we set it to gray and put into queue.
3. Set the parent of $u$ to $v$ and set the level of $u$ to $level(v)+1$.