使用邻接表时，传统(单向)BFS的时间复杂度为O(V+E)。如果是双向BFS怎么办?
根据这里的答案，我知道:
- BFS将遍历1 + B + B^2 +…+ B^k个顶点;而
- 双向BFS将遍历2 + 2B^2 +…+ 2B^(k/2)个顶点。
但是我不知道如何在此基础上推导时间复杂度
我很确定时间复杂度也是0 (V+E)。
让我们想象下面的图:你有两棵具有相同深度的二叉树。然后对于每一个二叉树你将所有的叶节点连接到一个顶点，并将根节点连接起来。从连接二叉树叶子的两个点开始，我们会看到两种算法都必须查看每个顶点。双向也要看所有的边。但是单向可以跳过2^(d - 1) - 1条边(d是深度)。所以我怀疑用一个更复杂的算法来做双向运算是否值得。我的想法是，如果这些点"接近"，你可能会更快地找到解决方案。但是对于那些需要很长时间来计算的极端情况，它不起作用。
顺便说一句。遍历的顶点数充其量只是一个近似值，因为您丢弃了所有已经发现的顶点。所以这个数字可能比B^k小得多。