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

Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.