Breadth-First Search
Breadth-first search explores a graph in rings. It starts at one vertex, visits every neighbor one edge away, then every still-unseen vertex two edges away, and keeps expanding like that. A queue makes the order happen: new vertices join at the back while the oldest one leaves from the front.
That level-by-level order gives BFS its most useful guarantee. In an unweighted graph, the first time it reaches the goal it has used the fewest possible edges. Remember which vertex discovered each new one, walk those parent links backward from the goal, and the shortest path falls out.
On the grid, each open cell is a vertex and each move is an edge. Movement is up, down, left, or right. Draw walls, move S and E, then press Play. Blue cells are waiting in the frontier, muted green cells have been visited, gold is the current cell, and bright green is the final route. Back, Next, and the step slider let you inspect the run.
Try Costly shortcut. BFS still finds a route with the fewest moves, but it ignores the terrain values when choosing that route. Crossing a cell marked 5 costs five instead of one, so fewer moves can mean a higher total cost. The starting cell costs zero. Compare this with Dijkstra and A* as those pages launch.
Open the node-and-edge demonstration below the grid to explore connected graphs, general trees, and binary trees with a visible queue and highlighted source. BFS takes O(V + E) time and O(V) auxiliary space; the visualizer stores extra snapshots so you can step backward.
Explore Breadth-First Search on a node-and-edge graph
A grid is one kind of graph. Try a connected graph, a general tree, or a binary tree to see the same traversal without the maze. These shapes are undirected and connected.
The queue holds discovered vertices waiting to be visited. The first route to the goal uses the fewest edges.