Overview

A depth-first search is an alogorithm used to traverse graphs. If you are familiar with data structures and algorithms (or have read my previous posts) you would know that a comparable algoriwthm would be breadth-first search. While the time and space complexity of DFS and BFS are the same, they are used in different situations based on the order of traversal.

The photo on the left shows a traversal of a graph using DFS, with the numbers representing when each node was visited beginning with the root. You can see some slight differences in comparison with BFS on the right which will visit every node at k distance before exploring any node at k + 1 distance. (please note: this is pre-order traversal, I will get into the pre/in-order/post later).

#

About the author
comments powered by Disqus