Breadth First Search

The basics to the breadth first search algorithm in computer science.

Summary

Breadth First Search is an algorithm used to explore the items in a structure. The most common data structures for this search are the tree and the graph. The main structure used to implement this algorithm is a queue, to keep track of the order in which we want to explore the items in the tree or graph. In the case of a graph, a set is also used to keep track of whether we have already explored a value in the graph. This is not needed for trees because they do not have cycles.

Algorithm Description

For Trees

1. Initialize queue with the first item in tree. We’ll call this queue items_to_visit.
2. Do steps 3–5 while you have items in items_to_visit. Skip to 6 when there are no more items.
3. Remove the top item from items_to_visit.
4. “Explore” this item…This could mean printing it, doing some math with it, etc. Whatever it is, you have “seen” this item.
5. Add all the “children” of the item you are exploring to items_to_visit.
6. When you have no more items in items_to_visit, you are done!

boinggg

For Graphs

1. Initialize a set for all the items you have visited. We’ll call this visited_items.
2. Initialize queue with the first item in the graph. We’ll call this queue items_to_visit.
3. Do steps 4–9 while you have items in items_to_visit. Skip to 10 when there are no more items.
4. Remove the top item from items_to_visit.
5. Check to see if this item is in the visited_items.
6. If it is in visited_items, skip 7 to 9 and start back again on step 3 with the next item.
7. If it is not in visited_items, “Explore” this item…This could mean printing it, doing some math with it, etc. Whatever it is, you have “seen” this item.
8. Once you’re done “exploring it”, add this item to visited_items.
9. Add all the “neighbors”, that have not been visited, of the item you just explored to items_to_visit.
10. When you have no more items in items_to_visit, you are done!

nodes in a network

Examples

For Trees

Let’s say we have the following tree. Assuming the first item is 👨🏾‍💻 and that we go from left to right when completing step 5 for adding the children, the order would be as follows: 👨🏾‍💻 → 🇳🇬 → 🗽 → 🥷🏾 → 🏈 → 🦂 → 🚴🏾‍♂️

If you understand why, comment below: I get it!! If you’re confused, ask me for an explanation in the comments below

Tree Diagram!

For Graphs

Let’s say we have the following graph. First of all notice the difference in how it looks from the tree. In the comments below, say what makes it different from the tree above. In this case, we may have a few different results since there is no left to right. So when considering neighbors, I’ll add them to the queue randomly. This will lead to a few different potential searches. You could avoid that by adding weights or making the items alpha numeric or w.e, but maybe next time… Anyways the order I got when starting from 👨🏾‍💻 is as follows: 👨🏾‍💻 → 🗽 → 🥷🏾 → 🚴🏾‍♂️ → 🏈 → 🇳🇬 → 🚴🏾‍♂️ → 🦂

If you understand why, comment below: I get it!! If you’re confused, ask me for an explanation in the comments below

Graph Diagram!

Practice Problems

For Trees

1. https://leetcode.com/problems/binary-tree-level-order-traversal/
2. https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
3. https://leetcode.com/problems/binary-tree-right-side-view/

For Graphs

1. https://leetcode.com/problems/number-of-islands/
2. https://leetcode.com/problems/cheapest-flights-within-k-stops/
3. https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/

I put the code to the general BFS algorithms in a package here. It’s written in python so it should be easy to read. Then if you would like to run it, go for it. I think all of that helps with understanding. If you’re still having trouble and maybe want to do a mock interview, you can schedule a 1 on 1 with me via Calendly. Thank you!