What is breadth first search?
Breadth first search (BFS) is an algorithm used to traverse a graph that contains a set of nodes and edges. The main objective is to perform a search of data by traversing the vertices connected by edges. It differs from its sister algorithm Depth first search (DFS) because it searches each level of vertices instead of going all the way down to the lowest level vertices [1].
Note that in figure 1 the algorithm starts at vertex 1, travels from 1 to 2, 1 to 3, and so forth. Graphics can be directed or undirected and as you can see the one shown in figure 1 is what is called an undirected graph with the arrows going in one direction. When using this type of graph, you generally don’t have a cycle, but it can happen, so any code implementation needs to double check for this situation.
How is this relevant to my life?
Much like DFS, BFS is used every day by the average Google user or other search platform like Yahoo. It also shows up in initial interviews or code challenges during the application process which can stump a would-be job seeker if they have not prepared properly because it can take a bit of practice to implement from scratch. This post will show a demonstration of the algorithm implemented iteratively and then recursively. Each approach has its advantages and disadvantages so if you know both ways you can do very well in questions related to this algorithm!
Final Thoughts
BFS is more than just an academic exercise—it’s a practical tool that powers everyday technologies. By exploring level by level, it ensures efficiency and fairness in traversal, making it a cornerstone of algorithmic problem-solving.
References
[1] Kahn Academy, “Breadth-first search and its uses” Retrieved from
Kahn Academy Breadth First Search on July 4th, 2023.