The breadth-first search is a tree traversal algorithm that searches a tree level by level. The search starts with the root node and works its way through every sibling node on a level before moving deeper into the tree. There are multiple ways to implement a breadth-first search. In this lesson, we will use an iterative approach that involves maintaining a collection of nodes in a frontier queue.
Here are the steps needed to implement this search algorithm:
- Import values into a tree data structure
- Determine the root node of the tree and the goal value to search for
- Create a queue of node paths that lead to the nodes that need to be searched
- Get a path from the queue to obtain the next node to search
- If the goal value isn’t found in the node, add a path to the queue for each of the node’s children
The iterative approach to the breadth-first search algorithm is also represented by the flow diagram next to the code editor. In this lesson, we’ll learn how to implement this algorithm in Python.
Run the code in the editor to see the breadth-first search in action.