Breadth first search branching factor

6
votes

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!

3
performancealgorithmartificial-intelligencebreadth-first-search
Strictly speaking d is NOT the depth of the graph. It is the depth of the shallowest solution. - nhahtdh
what do you mean by the shallowest solution? - runcode
If there are multiple solutions, and the solution are on different depth, then BFS will terminate when it has found one of the solution, which is the shallowest one. Unless you want to search the whole tree, then d might be defined differently. - nhahtdh
but when we talking about runtime, it is about the graph size, like how many edges on the graph. and we have to visit each edge for once, so the runtime is O(|E|).... right? - runcode

3 Answers

5
votes

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.

2
votes

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

1
votes

To quote from Artificial Intelligence - A modern approach by Stuart Russel and Peter Norvig:

Time and space complexity are always considered with respect to some measure of the prob- lem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, |V | + |E|, where V is the set of vertices (nodes) of the graph and E is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program. (The map of Romania is an example of this.) In AI, the graph is often represented implicitly by the initial state, actions, and transition model and is frequently infi- nite. For these reasons, complexity is expressed in terms of three quantities: b, the branching factor or maximum number of successors of any node; d, the depth of the shallowest goal node (i.e., the number of steps along the path from the root); and m, the maximum length of any path in the state space. Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we describe time and space complexity for search on a tree; for a graph, the answer depends on how “redundant” the paths in the state space are.

This should give you a clear insight about the difference between O(|V|+|E|) and b^d