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 a, travels from a to c, a to b, then c to e, then b to d and finally d to f. Graphics can be directed or undirected and as you can see the one shown in figure 1 is what is called a directed 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. A cycle would have a repeating set of vertices/edges such as a to b to c to a. The directional arrow tries to inform the reader of what paths are possible, so I generally like it over the undirected graph style.
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!
Real Examples
Iterative implementation
Recursive implementation
References
[1] Kahn Academy, “Breadth-first search and its uses” Retrieved from
Kahn Academy Breadth First Search on July 4th, 2023.