title: Breadth first search branching factor
body: <p>The run time of BFS is O(b^d)</p>
  
  <p>b is the branching factor
  d is the depth(# of level) of the graph from starting node.</p>
  
  <p>I googled for awhile, but I still dont see anyone mention how they figure out this "b"</p>
  
  <p>So I know branching factor means the "# of child that each node has"</p>
  
  <p>Eg, branching factor for a binary Tree is 2.</p>
  
  <p>so for a BFS graph , is that b= average all the branching factor of each node in our graph.</p>
  
  <p>or b = MAX( among all branch factor of each node) ?</p>
  
  <p>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.</p>
  
  <p>Seems O(b^d) is not making sense at this case.</p>
  
  <p>Can someone explain a little bit. Thankyou!</p>