Breadth First Search

Breadth First Search (BFS) is a non-informed search for trees. It involves visiting the nodes closest to the root before spreading out.

Implementation

Unlike DFS which has a very small memory footprint, BFS uses memory like a hog. Since we want to visit the nodes closest to the root before we visit their children, we must store the children in a queue. At each iteration, we take out a child, check to see if she is the solution. If she is, exit quickly. If not, put her children in the queue and repeat.

Advantages

If the solution is very close to the root node, BFS will find it quickly. If you fear that the tree can be enormous, and you do not want it iterating very far away, BFS or Iterative DFS will do the trick.

Disadvantages

Unfortunately, as stated before, since BFS must put all the children of all the nodes it traverses, the queue can get quite big, especially if the branching factor is high.

Implementation

A Java implementation

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License