Breadth-First Search: What’s the BFD with the BFS?

As a budding software engineer I received my first taste of algorithms through watching a popular YouTuber present interview questions as coding challenges to other engineers. I was blown away by the complex problems that these engineers could solve in a matter of minutes by implementing specific algorithms with their code. I rushed to my favorite search engine to search all of these new terms I had been hearing. What is Kosaraju’s algorithm? What are strongly connected components? What is an articulation point or a bridge?? Every time I looked something up I realized there was a more rudimentary principle that I needed to learn first. This search led me all the way back to learning about graph representation as a whole.

Since you are reading this I’m going to assume you understand the basic principles of graph representation. If you don’t, there is a link at the end of this article that will certainly help get you well on your way. Until then, stick around and have some fun learning about this elementary algorithm. The breadth-first search (BFS) is a very common graph traversal algorithm to learn first anyway, along with it’s cousin the depth-first search.

The Algorithm

A BFS is a way of traversing a graph by visiting every node and edge in a well-defined order by marking each node as visited along the way. Specifically, a BFS starts at a defined node and visits all of its connected neighbors. These neighbors all possess one degree of separation from the start node. This is level one, or layer one. Once level one has been cleared all the nodes in level two are visited, and so-on and so-forth. It is important to note that the nodes in each level are visited in a very specific order, as we will see in just a moment, and their children nodes are visited in this same order. This process continues until every node in the graph has been visited, or the end node has been found.

The Algorithm and the Subway

To give a slightly more concrete example we are going to take a look at the NYC subway system. The map below is in lower Manhattan. For the sake of this exercise we are only using a handful of subway stations, because this graph could become very large and complicated very quickly if we didn’t.

A snapshot of downtown Manhattan subway lines.

How the subway system would look at a graph. The nodes are the stations, and the edges are the tracks between each station.

Although it seems obvious, the start node is checked first. The node begins in the queue, is popped from the queue, and compared to the node we are searching for. Since it is not the node we are looking for, it is marked as visited by being placed in the visited set. Red nodes represent nodes that are cleared. Yellow nodes represent nodes that are being checked.

We traverse the graph in order. Since level 0 is clear, we move on to level 1. Each node is compared to the end node, and if it isn’t the node we are looking for, pushed to both the visited set and the queue.

The queue is then popped and checked, one by one, in the order they were received. Think first in, first out. Since Union Square was queued first from every node in level 1, its destinations are checked first. Level 2 is cleared, and the pattern continues.

Finally, we find Grand St at level 3.

Of course, we know that the Grand St station is connected to the 6th Ave L train one way or another. The subway system wouldn’t be much good (stop snickering New Yorkers) if the stops weren’t connected. However, if we were to imagine a connection going down due to track maintenance, we can see how the graph wouldn’t ever touch the Grand St node.

The Algorithm, in JS

Here is the code that I used to create a basic breadth-first search. There are many ways that this code could be altered to achieve slightly different results. With a few lines of code we could track the shortest path to the Grand St station, should one exist. This is more of a jumping off point. Use this to get you started, and then have fun playing around with it!

(Caution! This string won’t work properly when you .split() it due to the presence of \n. It’s poor form on my part, but I made the string three lines instead of one only for visibility in the screenshot.)

These are all of the connections between the subway stops in this section of NYC. Columbus Circle and 66th St are included to show how they won’t ever be touched by the search.

We use Map( ) here to create our adjacency list, because Map comes with methods that we are able to call such as .set( ) and .get ( ).

This is the output when you console.log(adjacencyList)

Here we use Set( ) to insure there are no duplicate values.

We can use node to run the code. My file was named nycbfs.js.

What the terminal prints out when we add this to the ‘else if’ conditional: console.log(`${destination} pushing to queue and added to visited`). Hopefully this helps visualize the order in which the BFS works.

This link will help get you started if you are still having trouble understanding graph representation. They have fantastic visuals as well as great explanations of complex material far beyond this algorithm.

https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/tutorial/