为什么双向广度优先搜索的时间复杂度仍为O(V+E)？

首先要明确，两种时间复杂度描述的是不同场景下的情况：

• 当用分支因子b和距离d描述时，针对的是找到目标节点就停止的场景：

  • 常规BFS需要遍历从起点出发的d层所有节点，总数约为O(b^d)
  • 双向BFS同时从起点和目标节点出发，各遍历d/2层，总节点数约为O(b^(d/2))，这种场景下效率提升显著，尤其是当d较大时。

• 当用顶点数V和边数E描述时，针对的是遍历完整个图的场景：

  • 不管是常规BFS还是双向BFS，最终都需要访问所有可达的顶点和边。双向BFS只是从两端同时推进，但本质上还是要覆盖所有节点和边，所以时间复杂度依然是O(V+E)——这和常规BFS遍历全图的复杂度完全一致。

总结一下：

• 找目标节点时，双向BFS靠减少遍历层数大幅提速；
• 遍历全图时，两者都要走完所有节点和边，复杂度自然相同。

内容的提问来源于stack exchange，提问作者Shisui