根据 Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig (Version 4) ，BFS 的空间复杂度为 O(b^d)，其中 'b' 是分支因子，'d' 是深度。
BFS 的复杂度是通过这个假设得出的:我们存储所有节点直到到达目标节点，换句话说: 1 + b + b^2 + b^3 + ... + b^d => O( b^d)
但是为什么我们要存储所有节点呢？我们不是用队列来实现吗？
如果我们使用队列，则不需要存储所有节点，因为我们分步骤将一些节点入队和出队，那么当我们找到目标节点时，我们可以说一些节点在队列中(但不是全部)他们)。
我的理解有误吗？
最佳答案
BFS 的问题在于，您本质上是并行追求多条路径。在深度优先搜索中，您只采用一个分支，一旦探索完该分支，其上的所有节点都可以出队。因此，您的队列中永远不需要超过一个分支的节点。
但在 BFS 中，你必须将每个分支保持在当前深度；你不能丢弃它们中的任何一个，因为它们还没有被充分探索。因此，您需要跟踪路径当前“头”节点的“历史”。在 DFS 中，一次只有一条路径，但在 BFS 中，有更多路径，具体取决于分支因子和当前深度。
关于data-structures - 广度优先搜索 (BFS) 算法的空间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/71814173/