4
$\begingroup$

Is the flood fill algorithm the same as depth first search?

If not, how do they differ in complexity?

$\endgroup$
8
$\begingroup$

The Flood Fill algorithm is a particular case of the Depth First Seach algorithm, on regular mesh graphs:

  • Wikipedia indicates that they do not work on the same kind of data:

    • The Flood Fill algorithm is "an algorithm that determines the area connected to a given node in a multi-dimensional array."

    • The Depth First Seach algorithm is "an algorithm for traversing or searching tree or graph data structures".

  • A multi-dimensional array (and the kind of neighborhood considered in the flood fill algorithm) is a particular case of graph, extremely regular.

In any case, the complexity is clearly within $O(n)$ where $n$ is the number of nodes being colored (for both problems).

$\endgroup$
  • $\begingroup$ DFS runs in $O(m)$ time. $\endgroup$ – Austin Buchanan Aug 22 '13 at 14:56
  • $\begingroup$ Floodfill can be implemented either with DFS or BFS, when all you care about is marking nodes with the same color. But when you also want to keep track of shortest distances, you'd better do a BFS rather than DFS. $\endgroup$ – Yibo Yang Feb 15 '16 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.