我最近被告知 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”版本?