Breadth-First Path Traversal

Algorithm

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

  1. Enqueue the first directory.
  2. Dequeue a directory from the queue.
  3. If the dequeued directory contains any directories, then enqueue the directories.
  4. Repeat at 2 until the queue 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


fuss/algorithms/path_traversal/breadth-first.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.