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.

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

Performance and Space Complexity

• Worst case performance:
• Worst case space complexity:

where is the number of edges and is the number of vertices.

Implementations

• AmigaOS C