Basic algorithm

The key idea for many search algorithms is to keep track of an expanding ring called the frontier.

We can search (or traverse) the graph by repeating these steps until the frontier is empty:

1. Pick and remove a location from the frontier.
2. Mark the location as visited so that we know not to process it again.
3. Expand it by looking at its neighbors. Any neighbors we haven’t we haven’t seen yet we add to the frontier.

Let’s see this up close. The tile are numbered in the order we visit them. Step through to see the expansion process:

Start the animation to see how the frontier expands for more steps:

We can implement this using just ten lines of (Python) code:

frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in visited:
         frontier.put(next)
         visited[next] = True

---