0

最近、BFSとDFSについて知らされ、DFSに何かを実装するように依頼されました。ディレクトリリスト/ファイル名の検索です。私はそれをやってのけることができました（公平に言えば、どのように進めるかについてのヒントを得ました）が、それ以来BFSに興味をそそられ、その概念を同じ問題。

ウィキペディアといくつかのグーグル検索で見つけた図に基づいて、これまでに得た最も近いものは次のとおりです。

コード：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.io.File;

public class foo {
    private List<List<String>> queue = new ArrayList<List<String>>();

    /**
     * @param args
     */
    public static void main(String[] args) throws Exception {
        foo f = new foo();
        f.traverse("src");
        f.report();
    }

    public void traverse(String dir) throws Exception {
        // add dir to the top of the tree
        queue.add(0, Arrays.asList(dir));
        traverse(dir, 1);
    }

    public void traverse(String dir, int depth) throws Exception {
        // add a new depth if this is a new one
        if (queue.size() <= depth) {
            queue.add(new ArrayList<String>());
        }

        File file = new File(dir);
        for (File curfile: file.listFiles()) {
            queue.get(depth).add(curfile.getPath());
            // recursive function call if curfile is a directory
            if (curfile.isDirectory()) traverse(curfile.getPath(), depth+1);
        }
    }

    public void report() {
        for (int i=0; i<queue.size()-1; i++) {
            log(String.format("****** Level %d ******", i));
            for (String node : queue.get(i))
                log(String.format("[%d] `%s'", i, node));
        }
    }

    public void log(String s) {
        System.out.printf("[foo] %s\n", s);
    }
}

出力：

[foo] ****** Level 0 ******
[foo] [0] 'src'
[foo] ****** Level 1 ******
[foo] [1] 'src/A'
[foo] [1] 'src/C'
[foo] [1] 'src/foo.java'
[foo] [1] 'src/B'
[foo] ****** Level 2 ******
[foo] [2] 'src/A/A2'
[foo] [2] 'src/A/A1'
[foo] [2] 'src/C/C1'
[foo] ****** Level 3 ******
[foo] [3] 'src/A/A2/A2A'
[foo] [3] 'src/A/A1/A1A'
[foo] [3] 'src/C/C1/C1A'
[foo] [3] 'src/C/C1/C1B'
[foo] ****** Level 4 ******
[foo] [4] 'src/A/A2/A2A/A2A1'
[foo] [4] 'src/C/C1/C1A/C1A1'
[foo] ****** Level 5 ******
[foo] [5] 'src/A/A2/A2A/A2A1/A2A1A'
[foo] ****** Level 6 ******
[foo] [6] 'src/A/A2/A2A/A2A1/A2A1A/A2A1A1'
[foo] [6] 'src/A/A2/A2A/A2A1/A2A1A/A2A1A2'

正しく見える出力を吐き出しますが、内部の仕組みが間違っていることを知っているので、これは正しくないことを私は知っています。これは本質的に、証拠を隠すためにArrayListを使用して、BFSを装ったDFSです。

この概念を理解しようと先延ばしを始めてから約1か月間、机に穴を開けるフレームワークの本を持っているので、誰かがここで閉鎖するのを手伝ってくれることを切に願っています。それで、たくさんのとりとめのないものに埋もれて、私の質問は、BFSをディレクトリ構造にどのように適用できるかということです。また、BFS / DFS実装例の「For-Dummies」バージョンはオンラインまたは印刷物でどこかにありますか？

4

1 に答える 1

0

BFS をディレクトリ構造にどのように適用できますか? BFS と DFS の両方の概念は、ツリー データ構造に関するものです (ディレクトリもツリーにすることができます)。ツリーの深さを理解していると仮定すると、BFS は基本的にすべてのノードを最小の深さから最大の深さの順に訪問します。キューが BFS にあるように、スタックは DFS にあります。

「ダミー用」の実装があるかどうかはわかりません。コンセプトは私が説明したのと同じくらい簡単だと思います。ウィキペディアは不足している情報を提供する必要があります。

実装についてどのような疑いがありますか? 前述のように、DFS と BFS の唯一の違いは、スタックまたはキューを使用することです。

于 2012-05-22T03:35:54.177 に答える