Graph Reductions: Flood Fill

Flood-fill problem using whatever-first search

One of the earliest modern examples of whatever-first search was proposed by Edward Moore in the mid-1950s. A pixel map is a two-dimensional array whose values represent colors; the individual entries in the array are called pixels, an abbreviation of picture elements. A connected region in a pixel map is a connected subset of pixels that all have the same color, where two pixels are considered adjacent if they are immediate horizontal or vertical neighbors. The flood fill operation, commonly represented by a paint can in raster-graphics editing software, changes every pixel in a connected region to a new color; the input to the operation consists of the indices $i$ and $j$ of one pixel in the target region and the new color.

The flood-fill problem can be reduced to the reachability problem by chasing the definitions. We define an undirected graph $G = (V, E)$ whose vertices are the individual pixels and whose edges connect neighboring pixels with the same color. Each connected region in the pixel map is a component of $G$ ...