Depth-First Path Traversal

Algorithm

A depth-first path-traversal uses a stack in order to remember directories as it scans. Initially, a directory is supplied which is scanned for directories in order to push them onto the stack. On every iteration, a directory is popped off the stack and similarly scanned in order to push any newly found directories. The algorithm terminates when the stack is empty.

Push the first directory.
Pop a directory from the queue.
If the popped directory contains any directories, then push the directories.
Repeat at 2 until the stack is empty.

Performance and Space Complexity

Worst case performance: $O(|E|)$
Worst case space complexity: $O(|V|)$

where $|E|$ is the number of edges and $|V|$ is the number of vertices.

Implementations

AmigaOS C