Algorithms For Dummies

 Challenging Difficult Problems

Processing vertex A, discovered ['F', 'G']

Processing vertex G, discovered ['K', 'H']

Processing vertex H, discovered ['B', 'D']

Processing vertex D, discovered ['E', 'J', 'C']

Processing vertex J, discovered ['O', 'I', 'N']

Processing vertex O, found no exit, retracing to J

Processing vertex N, discovered ['R']

Processing vertex R, discovered ['M', 'X']

Processing vertex X, discovered ['T', 'W', 'Y']

Arrived at final vertex Y

Unvisited vertices: 15

Best path is: ['A', 'G', 'H', 'D', 'J', 'N', 'R', 'X',

 'Y']

Length of path: 22

The  verbose  output  from  the  example  tells  you  how  the  algorithm  works.  BFS 

keeps moving until it runs out of vertexes to explore. When it exhausts the ver-

texes without reaching the target, the code tells you that it can’t reach the target 

and the robot won’t budge. When the code does find the destination, it stops pro-

cessing vertexes, even if 

open_list

 still contains vertexes, which saves time.

Finding a dead end, such as ending up in vertex O, means looking for a previously 

unused  route.  The  best  alternative  immediately  pops  up  thanks  to  the  prior-

ity  queue,  and  the  algorithm  takes  it.  In  this  example,  BFS  efficiently  ignores 

15  vertexes and takes the upward route in the map, completing its journey from  

A to Y in 22 steps.

You can test other mazes by setting a different seed number and comparing the 

BFS results with the A* algorithm described in the next section. You’ll find that 

sometimes BFS is both fast and accurate in choosing the best way, sometimes not. 

If you need a robot that searches quickly, BFS is the best choice.