Understanding depth first traversal on a grid

The depth-first algorithm on a grid is the same as for any other graph. We start from a node and recursively traverse all the unvisited neighbour nodes until no unvisited node remains in any paths originating at the start node. To fully traverse disconnected graphs, however, we need to iterate over all the nodes and run depth-first search from any unvisited node.

Depth-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 depth-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 depth-first search multiple times from different nodes.