Time complexity of traditional (one-way) BFS is O(V E) when an adjacency list is used. What is it in case of two-way BFS?

Based on the answer here, I know:

• BFS will traverse 1 B B^2 ... B^k vertices; whereas
• Bi-directional BFS will traverse 2 2B^2 ... 2B^(k/2) vertices.

But I don't know how to derive the time complexity based on this.

CodePudding user response：

I'm pretty sure that the time complexity is O(V E) too.

Let's imagine the following graph: You have two binary trees with the same depth. Then for each of the binary trees you connect all the leaves to a vertice and you connect the roots. Starting at the two points connected to the leaves of the binary trees we will see that both algorithms have to look at every vertex. Bi-directional has to look at all edges too. But one-way can skip 2^(d - 1) - 1 edges (d is the depth). So I somehow doubt that it is even worth it to have a more complex algorithm and do it bi-directional. My thought is that you might find a solution faster if the points are "close" but for the extreme cases that take the longest to calculate it doesn't help.

Btw. the number of vertices that are traversed is an approximation at best because you discard all vertices that were already discovered. So the number is probably a lot smaller than B^k.