A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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.

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:

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 ...