我们什么时候应该使用普通 BFS 而不是双向 BFS？

Question

我知道双向 BFS 比使用普通 BFS 有很多优势，因为理论上它可以将发现两个节点之间最短路径的时间以及查找一个节点是否可从另一个节点到达的时间减少一半。

我也明白，只有当我们唯一定义了两个节点时，我们才应该使用双向。

在什么情况下我们应该更喜欢普通的 BFS 而不是双向 BFS？

Answer 1

据我了解，双向 BFS 由给定起始节点和目标节点组成，从起始节点和目标节点交替扩展节点层，直到从两端到达中间的节点。从起点到目标的最短路径被理解为从起点到中间节点的最短路径，延续从中间节点到目标的最短路径。我可以看到，与标准 BFS 方法相比，可能需要扩展的节点更少。然而，

• 实现标准 BFS（sBFS）比实现双向 BFS（简称 bBFS）更容易。简单通常是好的，因为它更容易编码并随后验证其正确性。
• 如果图是有向且未加权的，sBFS保证它将以最少的步骤找到从起点到目标的最短路径；bBFS 不保证适用于有向图。
• 运行 sBFS 后，您可以重建从起始点到距离目标节点（即停止搜索之前）最多 1 步的所有节点的最短路径。这本身可能很有价值。运行 bBFS 不会生成这样的列表。

考虑到这一点，我认为 bBFS 仅适用于非常狭窄的情况（根据图表，预计它的性能比 sBFS 更好），而 sBFS 在更大范围的场景中既简单又有用。