☰

如何使用“find”进行广度优先搜索？

tag-icon • tag-icon find
如何使用“find”进行广度优先搜索？

主要-depth的find导致它执行深度优先搜索。

但是，默认顺序是不是广度优先搜索。

默认序列可以非正式地描述为“处理节点的深度优先遍历”。第一的遇到而不是在回溯过程中这样做。”

我确实需要广度优先搜索。我怎样才能让find自己有这样的行为呢？

为了便于说明，使用以下设置：

$ mkdir -p alpha/{bravo,charlie,delta}
$ touch alpha/charlie/{alpha,beta,gamma,phi}

find具有以下默认行为：

$ find alpha
alpha
alpha/charlie
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/delta
alpha/bravo

和-depth，它执行如下：

$ find alpha -depth
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/charlie
alpha/delta
alpha/bravo
alpha

但是，我想要的是以下（虚构的）选项：

$ find alpha -bfs
alpha
alpha/charlie
alpha/delta
alpha/bravo
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma

换句话说，我需要find处理/报告全部在进一步处理之前，先将文件/目录放置在给定的深度。

我怎样才能做到这一点？

答案1

# cat ./bfind

#!/bin/bash
i=0
while results=$(find "$@" -mindepth $i -maxdepth $i) && [[ -n $results ]]; do
  echo "$results"
  ((i++))
done

这是通过增加深度find和重复来实现的，我认为它可能会重复结果，但可以轻松过滤

答案2

您只需使用 shell 通配符即可做到这一点。建立一个具有逐渐更多目录级别的模式。

pattern='*'
set -- $pattern
while [ $# -ne 1 ] || [ "$1" != "$pattern" ]; do
  for file; do
    …
  done
  pattern="$pattern/*"
  set -- $pattern
done

这会丢失点文件。FIGNORE='.?(.)'在 ksh、shopt -s dotglobbash 或zsh 中使用来setopt glob_dots包含它们。

注意事项：

  • 如果有很多文件，这会耗尽内存。
  • 这会递归地遍历目录的符号链接。

如果您想选择目录和非目录的顺序，并且性能并不重要，则可以进行两次传递并[ -d "$file" ]在每次传递上进行测试。

答案3

您可以通过管道进行主要按路径名中的字符find数排序的排序。/例如，

find alpha |
awk '{n=gsub("/","/",$0);printf "%04d/%s\n",n,$0}' |
sort -t/ |
sed 's|[^/]*/||'

这用于awk在路径名前加上斜杠的数量，并sed在末尾删除此前缀。

实际上，由于您可能希望目录的内容alpha/charlie+列在 后面alpha/charlie，因此您需要指定sort -t/ -k1,1 -k2,2 -k3,3 -k4,4到所需的深度。

答案4

如果您只需要查找文件并且关心的是顺序而不是速度（即，如果您要列出数千个文件以进行交互式提示），则可以使用以下简单的解决方案：

find -depth -type f | tac

相关内容