Breadth First Search

Breadth first search is a common technique to search a tree data structure. As in the name, this algorithm traverses the tree shallow before going deeper. A tree usually consists of nodes or vertices that hold a value as well as point to other values, which links these items together in a tree like structure.

Let’s look at some pseudocode for how to implement the algorithm, this uses key value pairs to keep track of visited nodes and a queue to keep track of the next nodes to visit:

1. Pick a node to start with and add it to the queue
2. Mark the node at the front of the queue as visited
3. Take all of this node’s adjacent nodes that aren’t marked visited and add them to the back of the queue
4. Repeat steps 2 and 3 until the queue is empty

There, now we have visited every node in a tree. Notice that in step 4 we recursively call the method with the base case of the queue being empty. We have done this by going breadth first.

How does Breadth First Search(BFS) compare to Depth First Search(DFS)?

• BFS is faster when the node you are looking for is closer to the node you start on
• DFS generally uses less memory than BFS
• DFS us generally faster than BFS
• BFS uses a first-in first-out approach with a queue
• DFS uses a last-in first-out approach with a stack