Understanding breadth first traversal on a grid

The breadth-first algorithm on a grid is the same as for any other graph. We start from a node and all its unvisited neighbours to a queue to schedule their visit later. We then pick the node at the front of the queue and repeat the process until the queue is empty. However, to fully traverse disconnected graphs, we need to iterate over all the nodes and run breadth-first search from any unvisited node.

Breadth-first search on a grid uses coordinates (row, col) to uniquely identify a node and compute the identifiers (coordinates) of adjacent nodes, instead of reading them from an adjacency list. In this explanation, we will use the term cell and node interchangeably, as every node is uniquely identified by the coordinates (row, col) of its cell in the grid.