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 add 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.

Algorithm

To understand breadth-first search on a grid, let's consider a grid where a value of 1 indicates that the cell should be explored, while a value of 0 indicates it should not be explored. We can model this grid as a graph that has a mix of nodes, where some can be visited while others cannot. Since some cells also have 0 values, the resulting graph can potentially be disconnected, meaning there may not be a path between every pair of nodes. Therefore, we may need to run a breadth-first search multiple times from different nodes.