1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A single BFS from $s$ or $t$ would suffice. Why two? $\endgroup$ – hengxin Oct 8 '15 at 8:27
  • $\begingroup$ 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. $\endgroup$ – iluvAS Oct 8 '15 at 9:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 8 '15 at 11:16
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Oct 8 '15 at 13:11
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.