According to
Artificial Intelligence A Modern Approach – Stuart J. Russell , Peter Norvig (Version 4), space complexity of BFS is O(b^d), where ‘b’ is branching factor and ‘d’ is depth.
Complexity of BFS is obtained by this assumption: we store all nodes till we arrive to target node, in other word: 1 + b + b^2 + b^3 + … + b^d => O(b^d)
But why should we store all nodes? don’t we use queue for implementation?
If we use queue, don’t need to store all nodes, because we enqueue and dequeue some nodes in steps, then when we find target node(s), we can say some nodes are in queue (but not all of them).
Is my understanding wrong?
2
Answers
At any moment while we apply BFS, the queue would have at most two levels of nodes, for example if we just started searching in depth d, then the queue now contains all nodes at depth d and as we proceed the queue would finish all nodes at depth d and have all nodes at depth d+1, so at any moment we have O(b^d) space.
Also 1+b+b^2+…+b^d = (b^(d+1)-1)/(b-1).
The problem in BFS is that you essentially pursue a number of paths in parallel. In depth-first search, you take one branch only, and once that has been explored, all the nodes on it can be dequeued. So you never need more than one branch worth of nodes in your queue.
But in BFS you have to keep every branch up to the current depth; you cannot discard any of them, as they haven’t been fully explored yet. So you need to keep track of the ‘history’ of the current ‘head’-node of the path. In DFS there is only ever one path at a time, but in BFS there are more, depending on branching factor and current depth.