breadth first search breadth first search was first mentioned in chap the code for breadth first search differs in small way from depth first search instead of stacka queue is used to store the alternative choices the change to the code is smallbut the impact on the performance of the algorithm is quite big depth first search goes down one path until the path leads to the goal or no more steps can be taken when path is exhausted and does not end at the goalbacktracking occurs in contrastbreadth first search explores all paths from the starting location at the same time this is because each alternative is enqueued onto the queue and then each alternative is dequeued too this has an effect on how the search proceeds bfs example breadth first search takes step on each path each time through the while loop in sect soafter step in fig the two step ' occur next then the three step ' occur the three step ' are next the five step ' are all done on the next five iterations of the while loop you can see that the number of alternatives is growing in this maze there were step ' on up to five step ' the number of choices at each step is called the branching factor of problem branching factor of one would mean that there is no choice from one step to the next branching factor of two means the problem doubles in size at each step since breadth first search takes step in each direction at each stepa branching factor of two would be bad branching factor of two means the size of the search space grows exponentially (assuming no repeated statesbreadth first search is not good search in this case unless the goal node is very near the start node the breadth first search shown in fig covers nearly as much of the maze as the blind depth first search did only few locations are left unvisited the breadth first search found the optimal solution to this maze in factbreadth first search will always find the optimal solution if it is given enough time breadth first search also deals well with infinite search spaces because breadth first search branches out from the source exploring all possible paths simultaneouslyit will never get stuck going down some infinite path forever it may help to visualize pouring water into the maze the water will fill the maze from the source and find the shortest way to the goal the advantages and disadvantages of breadth first search are as follows breadth first search can deal with infinite search spaces breadth first search will always find the optimal goal it may not perform well at all when the problem has too high branching factor in factit may take millions of years or more to use breadth first search on some problems this copy belongs to 'acha