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'

我知道这不可能是正确的，因为尽管它吐出的输出看起来正确，但我知道内部运作是错误的。它本质上是一个伪装成 BFS 的 DFS，使用 ArrayList 来隐藏证据。

非常希望有人可以帮助我在这里结束，因为自从我开始拖延试图理解这个概念以来，我已经有一本框架书在我的桌子上烧了将近一个月。因此，埋头于大量的杂乱无章，我的问题是：BFS 如何应用于目录结构？此外，是否有在线或任何地方印刷的 BFS/DFS 实施示例的“For-Dummies”版本？

4

1 回答 1

0

BFS 如何应用于目录结构？BFS 和 DFS 的概念都是关于树数据结构的（目录也可以是树）。假设您了解树的深度，BFS 基本上是按照从最低深度​​到最高深度的顺序访问所有节点。Stack 之于 DFS 就像 Queue 之于 BFS。

我不确定是否有“傻瓜”实现。我认为这个概念和我解释的一样简单。维基百科应提供缺失的信息。

您对您的实施有什么疑问？就像我说的，DFS 和 BFS 之间的唯一区别是使用堆栈或队列。

于 2012-05-22T03:35:54.177 回答