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 the starting node.

I googled for a while, but I still don't see anyone mention how they figure out this "b"

So I know branching factor means the "# of the child that each node has"

Eg, the 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 have 10000 branchings, and all the rest 29955 nodes just have 10 branchings. and we have the depth set up to be 100.

Seems O(b^d) are not making sense in this case.

Can someone explain a little bit? Thank you!

Answer 1

The branching factor is the number of children at each node, the outdegree. If the branching factor is not uniform, an average branching factor can be calculated. 

The average branching factor can be quickly calculated as the number of non-root nodes (the size of the tree, minus one) divided by the number of non-leaf nodes.

Higher branching factors compose algorithms that follow every branch at every node, such as exhaustive brute force searches, computationally more expensive due to the exponentially increasing number of nodes, leading to combinatorial explosion.

The runtime of 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.

O(b^d) is used when using BFS mode is 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.

In such cases, because the graph is almost 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. O(m + n) is in the context of a graph search. O(b ^ d) is in the context of a tree search.

If you are looking to learn more about Artificial Intelligence then visit this Artificial Intelligence Course which will cover topics like Euclidean distance, Pearson Correlation Coefficient, Brute Force Algorithms, traveling salesman problem, NeuroEvolution of Augmenting Topologies, Fitness Function, Resolution Algorithm, k-nearest neighbors algorithm, Markov Model, Genetic Algorithm, deep first iterative deeping and many more.