Non-recursive implementation of Flood Fill algorithm?

Question

I'm working on a small drawing application in Java. I'm trying to create a 'bucket-fill' tool by implementing the Flood Fill algorithm.

I tried using a recursion implementation, but it was problematic. Anyway, I searched around the web and it seems that for this purpose, a non-recursive implementation of this algorithm is recommended.

So I ask you:

Could you describe a non-recursive implementation of the Flood Fill algorithm? An actual code example, some pseudo-code, or even a general explanation will all be welcome.

I'm looking for simplest, or the most efficient implementation you can think of.

(Doesn't have to be Java specific).

Thank you

Solution 1

I'm assuming that you have some sort of a grid where you receive the coordinates of the location from where you would like to fill the area.

Recursive flood fill algorithm is DFS. You can do a BFS to convert it to nonrecursive.

Basically the idea is similar in both the algorithms. You have a bag in which the nodes that are yet to be seen are kept. You remove a node from the bag and put the valid neighbors of the node back into the bag. If the bag is a stack you get a DFS. If it's a queue you get a BFS.

the pseudocode is roughly this.

flood_fill(x,y, check_validity)
   //here check_validity is a function that given coordinates of the point tells you whether
   //the point should be colored or not
   Queue q
   q.push((x,y))
   while (q is not empty)
       (x1,y1) = q.pop()
       color(x1,y1)

       if (check_validity(x1+1,y1))
            q.push(x1+1,y1)
       if (check_validity(x1-1,y1))
            q.push(x1-1,y1)
       if (check_validity(x1,y1+1))
            q.push(x1,y1+1)
       if (check_validity(x1,y1-1))
            q.push(x1,y1-1)

NOTE: make sure that check_validity takes into account whether the point is already colored or not.

---

• DFS: Depth First Search
• BFS: Breadth First Search

Solution 2

You basically have two ways to implement a flood fill algorithm non-recursively. The first method has been clearly explained by sukunrt in which you use a queue to implement breadth first search.

Alternatively, you can implement the recursive DFS non-recursively by using an implicit stack. For example, the following code implements a non-recursive DFS on a graph that has nodes as integers. In this code you use an array of Iterator to keep track of the processed neighbors in every node's adjacency list. The complete code can be accessed here.

public NonrecursiveDFS(Graph G, int s) {
        marked = new boolean[G.V()];

        // to be able to iterate over each adjacency list, keeping track of which
        // vertex in each adjacency list needs to be explored next
        Iterator<Integer>[] adj = (Iterator<Integer>[]) new Iterator[G.V()];
        for (int v = 0; v < G.V(); v++)
            adj[v] = G.adj(v).iterator();

        // depth-first search using an explicit stack
        Stack<Integer> stack = new Stack<Integer>();
        marked[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (adj[v].hasNext()) {
                int w = adj[v].next();
                if (!marked[w]) {
                    // discovered vertex w for the first time
                    marked[w] = true;
                    // edgeTo[v] = w;
                    stack.push(w);
                }
            }
            else {
                // v's adjacency list is exhausted
                stack.pop();
            }
        }
    }

Comments

[Tomasz Bielaszewski]

Your answer does not provide SSCCE and it is hard to understood your algorithm without it.

[LifeInTheTrees]

Hey, watch this video, sorry about the audio quality, tell me what you think: youtube.com/watch?v=LvacRISl99Y