time and space complexities of breadth first search

i dont understand how the following complexities come from.

espeacialy b(b^d-1) in the time complexity

Time complexity: Total numb. of nodes generated: 1 + b + b2 + … + bd + b(b^d-1) = O(b^(d+1)) Space complexity:O(b^(d+1))

where b – maximum br开发者_如何学JAVAanching factor of the search tree d – depth of the least-cost solution

---

At the root, you expand out b nodes as the next elements in the search tree. These, if none are the solution, in turn expand out b nodes from each. This continues until a solution is found, which will be at depth d.

Hence: O(b^d)

(I'm not sure where you got the +1 from, however...)

---

In simpler terms in BFS we make use of a queue to keep tract of the visited path . Every vertex in the graph is visited at most once . Hence the queue size is maximum V . Hence the space complexity if a function of the number of vertices in the graph i.e O(|V|). As regards to the time complexity we run a loop to go over all the vertices in the graph . This is O(|V|) . Also for every vertex found we need to check alls its neighbours and hence the number of edges it is connected to . THis gives us O(|E|) . Thus the complexity can be explained by the notation O(|V| + |E| ) .

---

If the algorithm were to apply the goal test to nodes when selected for expansion, rather than when generated, the whole layer of nodes at depth d would be expanded before the goal was detected and the time complexity would be O(b^(d+1)).