Can 'Find' or Any Other Tool Search for Files Breadth-First

Can 'find' or any other tool search for files breadth-first?

Yes, sort of.

You can use the -depth option to make it process a directory's contents before the directory itself. You can also use the -maxdepth option to limit how many directories down it will drill.

What is breadth-first search useful for?

When you want to reach a node by traversing as few edges as possible, i.e. when you want to find the shortest path in an unweighted graph.

Also the space complexity of a depth first search can be higher than that of a breadth first search when e.g. each node has only one child node, i.e. when the graph is deep but not very broad.

How to find all files containing specific text (string) on Linux?

Do the following:

grep -rnw '/path/to/somewhere/' -e 'pattern'

• -r or -R is recursive,
• -n is line number, and
• -w stands for match the whole word.
• -l (lower-case L) can be added to just give the file name of matching files.
• -e is the pattern used during the search

Along with these, --exclude, --include, --exclude-dir flags could be used for efficient searching:

• This will only search through those files which have .c or .h extensions:

  grep --include=\*.{c,h} -rnw '/path/to/somewhere/' -e "pattern"
  

• This will exclude searching all the files ending with .o extension:

  grep --exclude=\*.o -rnw '/path/to/somewhere/' -e "pattern"
  

• For directories it's possible to exclude one or more directories using the --exclude-dir parameter. For example, this will exclude the dirs dir1/, dir2/ and all of them matching *.dst/:

  grep --exclude-dir={dir1,dir2,*.dst} -rnw '/path/to/search/' -e "pattern"
  

This works very well for me, to achieve almost the same purpose like yours.

For more options, see man grep.

Does POSIX ls -R dictate a specific traversal order? If not, then which assumption is more likely to be portable: depth-first or breadth-first?

coreutils is indeed depth first. busybox is depth first. BSD/OS X is depth first (experimentally; the source is unreadable). I would expect most implementations to be depth first, because it's easy to do recursively and because the POSIX limit on path lengths bounds the memory/stack usage of depth first traversal pretty tightly.

---

Related Topics