11

私はJavaで小さな描画アプリケーションに取り組んでいます。フラッド フィル アルゴリズムを実装して「バケット フィル」ツールを作成しようとしています。

再帰の実装を試してみましたが、問題がありました。とにかく、私は Web を検索しましたが、この目的のために、このアルゴリズムの非再帰的な実装が推奨されているようです。

だから私はあなたに尋ねます：

Flood Fill アルゴリズムの非再帰的な実装について説明していただけますか? 実際のコード例、いくつかの疑似コード、または一般的な説明さえも歓迎します。

あなたが考えることができる最も単純な、または最も効率的な実装を探しています。

(Java 固有である必要はありません)。

ありがとうございました

4

3 に答える 3

7

フラッド フィル アルゴリズムを非再帰的に実装するには、基本的に 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();
            }
        }
    }
于 2014-02-21T11:22:48.533 に答える