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

Question

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

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

所以我问你：

你能描述一下洪水填充算法的非递归实现吗？一个实际的代码示例，一些伪代码，甚至一个一般的解释都是受欢迎的。

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

（不必是特定于 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。在此代码中，您将使用迭代器数组来跟踪每个节点邻接列表中已处理的邻居。完整的代码可以在这里访问。

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