Breadth-First Search (BFS)
Published:
This post explains the breadth-first search graph traversal algorithm. It is full of interactive examples that I used as part of my lectureship application at Swansea University.
Say we have a maze, and we want to find the shortest route from the entrance to the exit. We can encode that maze as a graph and use BFS to solve it. On the maze below, you can hit play() to see the algorithm explore the maze, shown in green. Notice how it flows through like water; whenever it reaches a fork, it explores all the possible paths simultaneously until it has explored the entire maze.