根据《人工智能现代方法》 – Stuart J. Russell 和 Peter Norvig（第四版），BFS的空间复杂度为O(b^d)，其中’b’是分支因子，’d’是深度。

BFS的复杂度是基于这样的假设得出的：我们需要存储所有节点直到到达目标节点，换句话说：1 + b + b^2 + b^3 + … + b^d => O(b^d)

但为什么我们需要存储所有节点呢？我们不是使用队列来实现的吗？

如果我们使用队列，就不需要存储所有节点，因为我们会在步骤中入队和出队一些节点，然后当我们找到目标节点时，可以说一些节点在队列中（但不是所有节点）。

我的理解有误吗？

回答：

BFS的问题在于你实际上是并行地追踪多个路径。在深度优先搜索中，你只选择一个分支进行探索，一旦该分支被探索完毕，其上的所有节点都可以出队。因此，你在队列中永远不需要超过一个分支的节点。

但在BFS中，你必须保留当前深度的所有分支；你不能丢弃任何一个，因为它们尚未被完全探索。因此，你需要跟踪当前路径的’头’节点的历史。在DFS中，任何时候都只有一条路径，但在BFS中，根据分支因子和当前深度，可能有更多的路径。