1
$\begingroup$

I am trying to prove that bidirectional BFS could have a worse run time than regular BFS. I am confused on how this would be possible, considered bidirectional BFS always divides the run time in two, since it is executing two searches. Would a specific order of nodes and vertices have to take place in order to give bidirectional a worse running time? Or is it a quantity issue?

Edit: Here is a graph I made. I'm assuming bi-directional BFS would infinitely search in this instance because if search one went right, and search two went left, they wouldn't find a path. Then, search one would go left, and search two would go right. Doesn't this mean that the search would run infinitely, because it doesn't stop until both have found the same path? enter image description here

$\endgroup$
2
  • $\begingroup$ What makes you think bidirectional BFS could have a worse run time than regular BFS? Did you read something that gave you that impression? If so, can you edit the question to provide additional context about where you ran across that suggestion? The answer might depend on how you measure the asymptotic time (i.e., as a function of what variables). Do you know how you want to measure it? In algorithms we usually measure it as a function of $|V|$ and $|E|$, but in AI sometimes one uses other parameters (e.g., branching factor). $\endgroup$
    – D.W. ♦
    Apr 11, 2018 at 23:34
  • $\begingroup$ I am trying to prove that it has a worse run time for a homework question. We are measuring asymptotic time in |V| & |E|. I added a little more of my process trying to figure out how this could happen. $\endgroup$
    – Megan Byers
    Apr 11, 2018 at 23:46

1 Answer 1

Reset to default
3
$\begingroup$

When attempting to find a path from a source vertex $s$ to a target vertex $t$, with both BFS and bi-directional BFS, if you assume a fairly steady branching factor $b$, the number of possibilities checked (and hence the running time) is dependent on the depth. For BFS the depth is the distance from the source to the target, giving $b^{k}$ vertices visited, for bi-directional BFS the two searches meet in the middle, so it's two lots of half-distance searches - $2\cdot b^{k/2} = 2\cdot\sqrt{b^{k}}$, which is clearly better.

So to get a worse time, you need a route from $s$ to $t$ that traverses very few vertices, but the route from $t$ to $s$ would visit many vertices. Essentially you want an asymmetric branching factor.

The family of star graphs would be sufficient for this. A star graph has a single central vertex, and all other vertices are connected directly to it, and no other vertices. So if you have $s$ as one of the pendent vertices, and $t$ as the central vertex, normal BFS would take constant time, and bi-directional BFS would take linear time. You can also invent more complicated examples that share this property of a low branching factor going one way, but a high one coming the other (up to a point).

$\endgroup$
1
  • $\begingroup$ @MeganByers no problem :) $\endgroup$
    – Luke Mathieson
    Apr 12, 2018 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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