双向BFS的时间复杂度是多少？该如何推导计算？

讨论前提：无权图、邻接表存储结构，设图中每个节点的平均出度为B，起点到终点的最短路径长度为k。

推导逻辑 #

邻接表存储下，BFS的总操作数和遍历节点数是同阶的：每访问1个新节点，就要遍历该节点的所有邻接边判断访问状态，总边访问量和总节点数成固定比例（比例系数为平均出度B），因此可以直接通过遍历节点数的量级推导时间复杂度。

你已知的两组遍历节点数结论，对应两种BFS的扩散过程：

• 单向BFS从起点单端逐层扩散，到第k层碰到终点时，总遍历节点数是公比为B的等比数列和：1 + B + B² + ... + B^k，量级为O(B^k)，最坏情况遍历全图所有节点和边，对应时间复杂度O(V+E)。
• 双向BFS从起点、终点两端同时扩散，每次优先扩展节点数更少的一侧，当两侧搜索边界相遇时终止，此时两端各自扩散的层数约为k/2。你看到的“双向BFS遍历顶点总数为 2 + 2B² + ... + 2B^(k/2)”是省略了低阶项的简化表达，完整求和结果为2*(1 + B + B² + ... + B^(k/2))，量级为O(B^(k/2))。

大O表示法会自动忽略常数系数和低阶项，因此不需要纠结求和式里缺省的低次项，核心是指数项的幂次从k降到了k/2。

最终复杂度结论 #

• 常规连通场景（起点终点连通、最短路径长度k较大）：双向BFS的时间复杂度量级为O(B^(k/2))，相比单向BFS的O(B^k)是平方根级别的效率提升，路径越长优化效果越明显。举个直观例子：若每个节点平均出度为10，最短路径长度为6，单向BFS需要遍历约111万个节点，双向BFS仅需要遍历约2200个节点，效率差三个数量级。
• 最坏场景（起点终点不连通、或最短路径长度极短）：双向BFS依然需要遍历完整连通分量的所有节点和边，最坏时间复杂度和单向BFS一致，为O(V+E)。

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