Depth-First Search vs. Breadth-First Search in Python
The simplified explanation of the two traversals algorithm.
When it comes to learning, there are generally two approaches: we can go wide and try to cover as much of the spectrum of a field as possible, or we can go deep and try to get specific with the topic that we are learning. Most good learners know that, to some extent, everything we learn in life — from algorithms to necessary life skills — involves some combination of these two approaches.
In this note, we will see two of the most basic searching algorithms — Depth-First Search and Breadth-First Search, which will build the foundation of our understanding of more complex algorithms.
The structure of this note:
- Tree traversal
- Depth-First Search
- Breadth-First Search
- Depth-First Search vs. Breadth-Frist Search
Let’s begin with tree traversal first.
What does it even mean to traverse a tree?
Since trees are a type of graph, tree traversal or tree search is a type of graph traversal. However, traversing through a tree is a little different from the more broad process of traversing through a graph.
