BREADTH-FIRST SEARCH

Introduction:

Breadth-first search is one of the flexible basis for implementing graph search stategies.

Consider the graph represented in the above figure. States are leveled as A,B,C,D.... . Breadth-first search explores the state in a level -by-level fashion. Only when there are no more states to be explored at a given level does the algorithm move on to the next level. A breadth-first search of the above graph considers the states in the order A, B, C, D, E, F, G, H, I, J, K.

Interpretation of Results:

To control the starting of demonstation, there is a sphere in the VRML image. If a student clicks on the sphere, the ball starts to move. The ball explores the state in a level-by-level fashion. First it will go to the first level. After that it will go to the second level. After exploring of all states in that level it will go to the third level. The ball will stop to explore if there are no more states to be explored ohterwise it will continue its exploration.

Figure 1: Breadth-first search

To see breadth-first search demonstration, CLICK on the above picture.

Back