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