Breadth first search branching factor
The run time of BFS is O(b^d)
b is the branching factor d is the depth(# of level) of the graph from starting node.
I googled for awhile, but I still dont see anyone mention how they figure out this "b"
So I know branching factor means the "# of child that each node has"
Eg, branching factor for a binary Tree is 2.
so for a BFS graph , is that b= average all the branching factor of each node in our graph.
or b = MAX( among all branch factor of each node) ?
Also, no matter which way we pick the b, still seeming ambiguous to approach our run time. For example , if our graph has 30000 nodes, only 5 nodes has 10000 branching, and all the rest 29955 nodes just have 10 branching. and we have the depth setup to be 100.
Seems O(b^d) is not making sense at this case.
Can someone explain a little bit. Thankyou!
Answer
The runtime that is more often quoted is that BFS is O(m + n) where m is the number of edges and n the number of nodes. This is because each vertex is processed once and each edge at most twice.
I think O(b^d) is used when using BFS on, say, brute-forcing a game of chess, where each position had a relatively constant branching factor and your engine needs to search a certain number of positions deep. For example, b is about 35 for chess and Deep Blue had a search depth of 6-8 (going up to 20).
In such cases, because the graph is relatively acyclic, b^d is roughly the same as m + n (they are equal for trees). O(b^d) is more useful as b is fixed and d is something you control.