Mathematical representation of flood fill algorithm

Question

For school I'm writing a report on the flood fill algorithm used in computing. I was wondering if the flood fill algorithm can be represented mathematically, I've searched all over but cannot find anything. If so, can you provide any sources for your answer so I may use them as a reference in the report?

Answer 1

Looking at the wikipedia article, some mathematical concepts that show up are

• a finite number of picture elements (pixels) that have a colour assigned each
• these form a grid of square cells (but the idea should work for e.g hexagonal cells too, see graph for the general case) which is the picture
• each pixel can be addressed by coordinates or a number, they are enumerated
• there is a neighbourhood relation that relate two pixels or not (e.g. four neighbour or eight neighbour relations)
• how to traverse along the pixels of your grid (recursion or some sort of list can be used to organize this) for checking and changing colour
• analysis of time and memory needed to perform the algorithm for a given picture

Note that the article gives no reference for the origin of the presented algorithm. It showed up in the 80ies home computer era in graphics programs, but is likely to have been used on earlier hardware as well.

Answer 2

The flood fill algorithm is a typical application of depth-first search in graphs, though it can be implemented using breadth-first search.

The graph is the one induced by the grid of pixels.