Elementary Foundations: An introduction to topics in discrete mathematics

Look for a vertex $y$ of $G$ which is adjacent to $x$ but not already in $T\text{.}$ If such a $y$ is found, go to Step 2. Otherwise, go to Step 3.

Adjoin $y$ and a single edge between $x$ and $y$ to $T\text{.}$ If $y=v^{\prime }\text{,}$ stop — a path from $v$ to $v^{\prime }$ exists and is now contained in $T\text{.}$ Otherwise, set $x=y$ and return to Step 1.

If you have arrived here immediately after beginning the algorithm (i.e. with $x$ still set to be $v$), stop — there is no path from $v$ to $v^{\prime }\text{.}$ Otherwise, return to the vertex $z$ adjoined before $x\text{.}$ Set $x=z$ and return to Step 1.

For each vertex $x$ in $T$ added in the last application of this step (or, in the case of the first application of this step, for $x=v$), adjoin all vertices of $G$ that are adjacent to $x$ and not already in $T\text{,}$ along with a single edge between each such vertex and $x\text{.}$ If at least one vertex has been adjoined to $T$ in this step, proceed to Step 2. Otherwise, stop — there is no path from $v$ to $v^{\prime }$ in $G\text{.}$

If $v^{\prime }$ was one of the vertices adjoined in Step 1, stop — a path from $v$ to $v^{\prime }$ exists and is now contained in $T\text{.}$ Otherwise, return to Step 1.