Main loop of graph search

from Red Blob Games
DRAFT
Sep 2014, then Jul 2020

My goal is to show how the code for breadth first search works by watching the changes to the variables as it runs. The frontier and current frontier node are blue; the neighboring nodes and next neighbor are green.

{missing: visualization of the graph, and something pointing out that *some* links from the frontier current node will point into the reached nodes and some will point into unexplored nodes; I’m using brown vs gray to distinguish these}

The reached set is everything we’ve seen; the frontier is everything we still need to look at. The frontier is the right hand side of the reached set.

 1  reached = [] 
 2  frontier = Queue() 
 3  reached.append(start)
 4  frontier.put(start)
 5  
 6  while not frontier.empty():               
 7     current = frontier.get()               
 8     for next in graph.neighbors(current):   
 9       if next not in reached:              
10           reached.append(next)             
11           frontier.put(next)               
                                              

Things to note:

  1. The frontier queue is a trailing sliding window of the reached set.
  2. When a neighboring node is already in reached, it can be skipped. If it’s not already in reached, then we add it to both  reached and frontier.
  3. Since frontier is a queue, we remove current on the left and we insert next on the right.

TO DO:

  1. Make the graph smaller. Too many nodes to wait through.
  2. Add a visualization of the graph that this is searching over.
  3. Make it so that you click on the next node to process, instead of running by itself.