A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Breadth-First Search

Breadth-first search, often abbreviated BFS, is another way to search a graph. Unlike depth-first search, breadth-first search does not use recursion. Instead, the algorithm revolves around our old friend, the queue. As you’ll recall, the queue is a FIFO data structure, and whatever goes in first, comes out first.

Let’s look at the algorithm for breadth-first search. As with our walk-through of depth-first search, we’re going to focus on graph traversal using breadth-first search; that is, we’re going to visit each vertex from our example social network.

Here’s the BFS traversal algorithm:

1. Start at any vertex within the graph. We’ll call this the starting vertex.

2. Add the starting vertex to the hash table to mark it as having ...