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

Get A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1 now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial