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.
Here is the algorithm for breadth-first search. As with our walkthrough 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 is the algorithm for breadth-first traversal:
Start at any vertex within the graph. We’ll call this the “starting vertex.”
Add the starting vertex to the hash table to mark ...