Main loop of graph search

Try out graph search yourself! The frontier and current frontier node are blue. Those are nodes we still need to look at. The neighboring nodes and next neighbor are green. Those are nodes we are currently looking at. The reached nodes are everything we’ve seen so far.

 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)               
                                              

If you visit the nodes in order of them being reached, it’s Breadth First Search:

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.

However, on this page you can visit in any graph search order. Depth First Search visits the most recently reached node first. Dijkstra’s Algorithm, Best First Search, and A* visit nodes in some type of priority order.