Flood Fill算法的非递归实现？

Question

我正在研究Java中的小型绘图应用程序.我正在尝试通过实施Flood Fill算法来创建"桶填充"工具.

我尝试使用递归实现,但这是有问题的.无论如何,我在网上搜索,似乎为此目的,建议使用此算法的非递归实现.

所以我问你:

你能描述Flood Fill算法的非递归实现吗？一个实际的代码示例,一些伪代码,甚至一般的解释都将受到欢迎.

我正在寻找你能想到的最简单或最有效的实现.

(不一定是Java特定的).

谢谢

Answer 1

我假设您有某种网格,您可以从中获得您想要填充该区域的位置坐标.

递归泛洪填充算法是DFS.您可以执行BFS将其转换为非递归.

基本上这两种算法的想法是相似的.你有一个包,其中保存了尚未看到的节点.您从包中删除节点并将节点的有效邻居放回包中.如果包是一个堆栈,你会得到一个DFS.如果它是一个队列你得到一个BFS.

伪代码大致是这个.

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)

注意:确保check_validity考虑该点是否已着色.

• DFS:深度优先搜索
• BFS:广度优先搜索

Answer 2

您基本上有两种方法可以非递归地实现泛洪填充算法.sukunrt已经清楚地解释了第一种方法,其中您使用队列来实现广度优先搜索.

或者,您可以使用隐式堆栈非递归地实现递归DFS.例如,以下代码在具有整数节点的图上实现非递归DFS.在此代码中,您使用Iterator数组来跟踪每个节点的邻接列表中的已处理邻居.完整的代码可以在这里访问.

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();
            }
        }
    }