<p>The <a href="http://en.wikipedia.org/wiki/Flood_fill" rel="noreferrer">Flood Fill</a> algorithm is a particular case of the <a href="http://en.wikipedia.org/wiki/Depth_first_search" rel="noreferrer">Depth First Seach</a> algorithm, on regular mesh graphs:</p>

<ul>
<li><p>Wikipedia indicates that they do not work on the same kind of data:</p>

<ul>
<li><p>The <a href="http://en.wikipedia.org/wiki/Flood_fill" rel="noreferrer">Flood Fill</a> algorithm is "an algorithm that determines the area connected to a given node in a <strong>multi-dimensional array</strong>."</p></li>
<li><p>The <a href="http://en.wikipedia.org/wiki/Depth_first_search" rel="noreferrer">Depth First Seach</a> algorithm is "an algorithm for traversing or searching <strong>tree or graph</strong> data structures".</p></li>
</ul></li>
<li><p>A multi-dimensional array (and the kind of neighborhood considered in the flood fill algorithm) is a particular case of graph, extremely regular.</p></li>
</ul>

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

CC BY-SA 3.0
2013-08-22T14:56:59.063Z
DFS runs in $O(m)$ time.
Austin Buchanan
CC BY-SA 3.0
2016-02-15T17:21:11.593Z
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.
Yibo Yang
CC BY-SA 3.0
2013-07-28T16:50:50.990Z
2013-08-22T12:07:26.047Z
2013-08-22T12:07:26.047Z
J.y B.y
<p>Is the <a href="http://en.wikipedia.org/wiki/Flood_fill" rel="noreferrer">flood fill algorithm</a> the same as <a href="http://en.wikipedia.org/wiki/Depth_first_search" rel="noreferrer">depth first search</a>?</p>

<p>If not, how do they differ in complexity?</p>

<graph-algorithms><time-complexity><graph-colouring>
Flood fill vs depth first search
gen
# Flood fill vs depth first search

(Asked by: username_0 on 2013-07-28)

Is the [flood fill algorithm](http://en.wikipedia.org/wiki/Flood_fill) the same as [depth first search](http://en.wikipedia.org/wiki/Depth_first_search)?

If not, how do they differ in complexity?

**Tags:** graph-algorithms, time-complexity, graph-colouring


---

## 1 answers

### Answer by username_1 on 2013-07-28. Score: 10 | Accepted answer

The [Flood Fill](http://en.wikipedia.org/wiki/Flood_fill) algorithm is a particular case of the [Depth First Seach](http://en.wikipedia.org/wiki/Depth_first_search) algorithm, on regular mesh graphs:

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

  + The [Flood Fill](http://en.wikipedia.org/wiki/Flood_fill) algorithm is "an algorithm that determines the area connected to a given node in a **multi-dimensional array**."
  + The [Depth First Seach](http://en.wikipedia.org/wiki/Depth_first_search) 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).

> **Comments:**
> **username_2**: DFS runs in $O(m)$ time.  
> **username_3**: 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.  

---

