# Starting BFS at s and t

INPUT: undirected graph, s, t

OUTPUT: connectivity of s and t

I perform BFS on s AND t, each taking turns to make one traversal.

When a vertex exists in both s and t's BFS tree, we can assume it is connected.

When one tree is done traversing but the other is not, s and t are not connected.

Does such an algorithm exist or am I making stuff up?

• A single BFS from $s$ or $t$ would suffice. Why two? – hengxin Oct 8 '15 at 8:27
• in a scenario where I remove an edge and let $s$ and $t$ be the two vertices the edge was bridging, I'd imagine this method will be faster? Unless they are disconnected and $|G_s - G_t| > G_s$ or $|G_s - G_t| > G_t$ then itll be slower. Not sure if its proven to work though, thats why im asking here. – iluvAS Oct 8 '15 at 9:12
• BFS finds shortest paths. Whether the basic or the double-ended version visits more nodes until it finds the shortest path depends on the graph. – Raphael Oct 8 '15 at 11:16
• @hengxin Because it's more efficient. Suppose that $\mathrm{dist}(s,t)=\ell$. Ordinary BFS may visit every vertex within distance $\ell$ of $s$, whereas bidirectional search only visits every vertex within distance $\ell/2$ of either $s$ or $t$. So, in a large (diameter bigger than $\ell$) $d$-regular graph, BFS visits about $d^\ell$ vertices, compared to only about $2\sqrt{d^\ell}$ for bidirectional search. – David Richerby Oct 8 '15 at 13:11

Yes, this is a known thing. It's called bidirectional search. It will find shortest paths in unweighted graphs and, in graphs of where every vertex has degree $d$, it will visit at most $2d^{\ell/2}=2\sqrt{d^\ell}$ vertices (where $\ell$ is the length of the shortest path), whereas ordinary BFS could visit up to $d^\ell$ vertices.