Breadth-first search

Remarks

Each vertex enters $Q$ at most once and each adjacency list is scanned once, so the running time is $O(\abs{V} + \abs{E})$. At the end, $d(v)$ is the distance from $s$ to $v$, the least number of edges of a path from $s$ to $v$. In particular $d(v) = \infty$ exactly when $v$ is not reachable from $s$. The parent pointers form a tree of shortest paths rooted at $s$. The key fact is that the vertices leave $Q$ in nondecreasing order of $d$.

Example: on the cycle with vertices $1, 2, 3, 4, 5$ and edges $\set{i, i+1}$ and $\set{5, 1}$, BFS from $1$ gives $d = (0, 1, 2, 2, 1)$.

Non-example: replacing the queue by a stack, so that the last vertex added is removed first, does not compute distances in general. On the same cycle, scan neighbours in increasing order. The stack pops $5$ and then $4$, so vertex $3$ is first reached from $4$ and gets the value $3$ instead of $2$.