ALGORITHMS: BREADTH - FIRST
Also an unintelligent searching algorithm, breadth-first searching expands a node and checks each of its successors for a goal state before expanding any of the original node's successors (unlike depth-first search).
Click here to see a shockwave demo (demo from http://www-jcsu.jesus.cam.ac.uk/~tdk22/project/breadthfirst.html).
Visited Nodes
|
Current Node
|
|
|
![]() ![]() |
The initial node is checked for a goal state, then expanded. |
Each of the initial node’s successors is then checked. |
Should all of the initial node’s successors fail to be a goal state, one successor is expanded... |
|
|
...and its successors checked. If none are goal states, a different successor of the initial node is checked. |
Thus, every node on a given “level” is checked before any node on a later level is checked. Should a node have no successors, there is simply nothing to expand, and the search proceeds to the next node on that level. |
This last observation is key in understanding the primary usefulness of the breadth first search—the most efficient solution (or, at least, a solution at least as efficient as any other solution) is guaranteed, since all possible states reached in less moves have already been checked, and are known not to be goal states. Related is the feature that a breadth-first search cannot get stuck in an infinite loop; since all possible states of a certain level are checked in order, the state(s) which break out of the loop will be evaluated and expanded (so will the ones in the loop, but unlike depth-first, there is no chance that the loop will be the only thing being checked—unless, of course, the only possible result from the initial state is an infinite loop).
Breadth-first’s primary drawback is in its use of memory. Since all possible paths are being considered step-by-step in tandem, nodes are essentially never deleted from memory until a goal is found. Also, since a breath-first search goes “deeper” much more slowly than a depth-first search, a problem with many solutions of all approximately the same depth will take much longer to solve with a breadth-first approach. For instance, a maze like this
with two paths of approximately equal length will be solved twice as fast with a depth-first search, which goes all the way down one path and finds the solution, rather than taking alternating steps down each path (assuming the depth first search does not get caught in an infinite loop!).