algorithm - 洪水填充算法的非递归实现？

Question

我正在使用 Java 开发一个小型绘图应用程序。我正在尝试通过实现洪水填充算法来创建一个“桶填充”工具。

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

所以我问你：

您能描述一下 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

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

Answer 3

编辑：观看此视频： https ://www.youtube.com/watch?v=LvacRISl99Y

我使用上述方法的结果是每秒大约 1000 万像素。我研究了它，在大约 2-3 分钟内用迷宫结构填充 20 亿体素空间，避免堆栈溢出。

我没有使用复杂的逻辑来跟踪先前验证过的相邻空间，而是有一个二维数组来记录所有验证过的空间。从已验证的数组中读取 2-3 条指令： IF 像素 [23,23] 已验证，然后填充它并检查它的邻居并将它们写入已验证的数组（填充像素 [23,23]，验证像素 [23+1 ,23]和其他三个。代码在视频中。