Breadth-first search

Given a graph $G$ and a source node $s$, breadth-first search systematically discovers every vertex available from $s$, producing a "breadth-first tree", where $s$ is the root and the simplest path in the tree from $s$ to an arbitrary vertex $v$ corresponds to the shortest walk from $s$ to $v$in $G$.