双向BFS的时间复杂性
传统（单向）BFS的时间复杂性是o（v+e）当使用邻接列表时。在双向BFS的情况下是什么？
基于答案在这里，我知道：
- bfs将穿越1 + b + b + b^2 + ... + b^k顶点；而
- 双向BFS将穿越2 + 2b^2 + ... + 2b^（k/2）顶点。
但是我不知道如何基于此得出时间复杂性。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我很确定时间复杂性也是O（v+e）。
让我们想象以下图：您有两个具有相同深度的二进制树。然后，对于每种二进制树，您将所有叶子连接到佛提比，然后将根连接起来。从连接到二进制树叶子的两个点开始，我们将看到两个算法都必须查看每个顶点。双向也必须查看所有边缘。但是单向可以跳过2^（d -1）-1边（D是深度）。因此，我以某种方式怀疑具有更复杂的算法并进行双向进行，甚至值得。我的想法是，如果要点“接近”，您可能会更快地找到解决方案，但是对于最长的时间来计算的极端情况并没有帮助。
顺便提一句。遍历的顶点数量充其量是一个近似值，因为您丢弃已经发现的所有顶点。因此，这个数字可能比b^k小很多。
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.