Breadth first search branching factor

Question

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 1

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.

Answer 2

in graphs O(b^d), the b = MAX. Since it is the worst case. check this link from princeton http://www.princeton.edu/~achaney/tmve/wiki100k/docs/Breadth-first_search.html - go to time complexity portion