I keep forgetting how BFS checks if the node is unexplored.
Like sometimes I just forget about it and turn it into a DFS and when I rememmber I want to check if the node is in the queue.
Just remember you only go down a row when you are down with the current row
Seriously why can’t I remember this.

Basically some gists from http://www.cs.toronto.edu/~krueger/csc263h/lectures/BFS.pdf.

1
2
3

graph TD;
  S-->U;
  U-->V;

$d$: depth from root
$\delta$: shortest path from root

Prove by contradiction:
$v$: closest node ( to $s$) where $d[v]\neq \delta(s,v)$.
$u$: the “predecessor” of $d$ on one of the shortest paths from $s$ to $v$.
Statement to contradict with :

• since predecessor, $\delta(s,u)+1=\delta(s,v)$.
• since $v$ closest and $u$ closer, $d[v]=\delta(s,u)$.
• from definition $d[v]\neq \delta(s,v)$.
• therefore $d[v]\neq \delta(s,v)=\delta(s,u)+1$
• since $d[v]$ is some kind of a path, and $\delta(s,v)$ is the shortest path by definition, $d[v]\geq \delta(s,v)$.
• Combine last 2 step and $d[v]>d[u]+1$.

Remark: basically deduce that between reaching the predecessor on shortest path and the vertex, the BFS visits at least 2 other nodes.

Three cases:

• $v$ not discovered:
  then $d[v]=d[u]+1$ since we will go to $v$ when exploring $u$’s neibours.

• $v$ is discovered and explored:
  Then it is enqued before $u$ thus $d[v]\leq d[u]$¹

• $v$ discovered but not fully explored
  Take the node that discovered $v$, this node is explored before $u$
  so by it is enqueued before $u$¹ $d[w]\leq d[u]$. Since $v$ discovered by $w$, $d[v]=d[w]+1\leq d[u]+1$

  ---

  Remark: the depth difference between $u$ and $v$ can’t be greater than 1 because we would explore all neighbours thus depth difference bettween neightbours cant be greater than $1$; and we know $u$ and $v$ have to be neighbours. Anyway the contradiction proof in other 2 cases uses property¹ but it is pretty intuitive that the depth difference can only be smaller.