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

3. Add the starting vertex to a queue.

4. Start a loop that runs while the queue isn’t empty.

1. Within this loop, remove the first vertex from the queue. We’ll call this the current vertex.

2. Iterate over all the adjacent vertices of current vertex.

3. If the adjacent vertex was already visited, ignore it.

4. If the adjacent vertex has not yet been visited, mark it as visited by adding it to a hash table, and add it to the queue.

5. Repeat this loop (starting from Step 4) until the queue is empty.

Breadth-First Search Walk-Through

This isn’t as complex as it seems. Let’s walk through the traversal step by step.

To set things up, let’s work with Alice as our starting vertex. We’ll mark her as visited and add her to the queue:

We now begin the core algorithm.

Step 1: We remove the first vertex from the queue and it make it the current vertex. This would be Alice, as she’s currently the only item in the queue. So at this point, the queue is empty.

Since Alice is the current vertex, we proceed to iterate over Alice’s adjacent vertices.

Step 2: We’ll start with Bob. We’ll mark him as visited and add him to the queue:

Note that Alice is still the current vertex, as indicated by the lines around her. However, we’ve still marked Bob as visited and added him to the queue.

Step 3: We move on to Alice’s other adjacent vertices. Let’s choose Candy; we’ll mark her as visited and add her to the queue:

Step 4: We then mark Derek as visited and add him to the queue:

Step 5: We do the same with Elaine:

Step 6: Now that we’ve iterated through all the neighbors of the current vertex (Alice), we remove the first item from the queue and make it the current vertex. In our case, Bob is at the front of the queue, so we dequeue him and make him the current vertex, as shown in the .

Since Bob is the current vertex, we iterate over all of his adjacent vertices.

Step 7: Alice has already been visited, so we ignore her.

Step 8: Fred has not yet been visited, so we mark him as visited and add him to the queue:

Step 9: Bob has no more adjacent vertices. This means we pull the first item out of the queue and make it the current vertex. This would be Candy:

We iterate over Candy’s adjacent vertices.

Step 10: Alice has already been visited, so we ignore her again.

Step 11: Helen, on the other hand, has not yet been visited. We mark Helen as visited and add her to the queue:

Step 12: We’re done iterating over Candy’s adjacent vertices, so we pull the first item from the queue (Derek), and make it the current vertex:

Derek has three adjacent vertices, so we iterate over them.

Step 13: Alice has already been visited, so we ignore her.

Step 14: The same goes for Elaine.

Step 15: This leaves Gina, so we mark her as visited and add her to the queue:

Step 16: We’ve visited all of Derek’s immediate friends, so we take Elaine off the queue and designate her as the current vertex:

Step 17: We iterate over Elaine’s adjacent vertices, starting with Alice. She’s already been visited, though.

Step 18: We’ve already visited Derek too.

Step 19: We pull the next person off the queue (Fred), and turn him into the current vertex:

Step 20: We iterate over Fred’s neighbors. Bob has already been visited.

Step 21: Helen also has already been visited.

Step 22: Since Helen is at the front of the queue, we dequeue Helen and make her the current vertex:

Step 23: Helen has two adjacent vertices. We’ve already visited Fred.

Step 24: We’ve also already visited Candy.

Step 25: We remove Gina from the queue and make her the current vertex:

Step 26: We iterate over Gina’s neighbors. Derek has already been visited.

Step 27: Gina has one unvisited adjacent friend, Irena, so we visit Irena and add her to the queue:

We’re now done iterating over Gina’s neighbors.

Step 28: We remove the first (and only) person from the queue, which is Irena. She becomes the current vertex:

Step 29: Irena has just one adjacent vertex, Gina, but Gina has already been visited.

We should now remove the next item from the queue, but the queue is empty! This means our traversal is complete.

Code Implementation: Breadth-First Search

Here’s our code for breadth-first traversal:

We begin by importing a queue_implementation module. This is simply the same queue implementation we created back in .

The bfs_traverse method accepts a starting_vertex, which is the vertex we begin our search from.

We start by creating the queue that fuels our algorithm:

We also create the visited_vertices hash table in which we keep track of which vertices we’ve already visited:

We then mark the starting_vertex as visited and add it to the queue:

We begin a loop that runs as long as the queue isn’t empty:

We remove the first item from the queue and make it the current vertex:

Next, we print the vertex’s value just to see in our console that our traversal is working correctly:

We then iterate over all the adjacent vertices of our current vertex:

For each adjacent vertex that hasn’t been visited, we add it to the hash table to mark it as visited and then add it to the queue:

And that’s the gist of it.

DFS vs. BFS

If you look carefully at the order of breadth-first search, you’ll notice that we first traverse all of Alice’s immediate connections. We then spiral outward and gradually move farther and farther from Alice. With depth-first search, though, we immediately move as far away from Alice as we possibly can until we’re forced to return to her.

So we have two methods of searching a graph: depth-first and breadth-first. Is one approach better than the other?

As you’ve probably caught on by now, it depends on your situation. In some scenarios, depth-first may be faster, while in others, breadth-first might be the better choice.

Usually, one of the main factors in determining which algorithm to use is the nature of the graph you’re searching and what you’re searching for. The key here, as mentioned earlier, is that breadth-first search traverses all the vertices closest to the starting vertex before moving farther away. Depth-first search, on the other hand, immediately moves as far away from the starting vertex as it can. Only when the search hits a dead end does it return back to the starting vertex.

So let’s say we want to find all the direct connections of a person in a social network. For example, we may want to find all of Alice’s actual friends in our earlier example graph. We’re not interested in who her friends’ friends are—we only want a list of her direct connections.

If you look at the breadth-first approach, you’ll see that we immediately find all of Alice’s direct friends (Bob, Candy, Derek, and Elaine) before moving on to her “second-degree” connections.

However, when we traversed the graph with the depth-first algorithm, we ended up touching Fred and Helen (two people who aren’t Alice’s friends) before finding Alice’s other friends. In a larger graph, we could waste even more time traversing many unnecessary vertices.

But let’s take a different scenario. Say our graph represents a family tree, which may look as follows:

This family tree shows all the descendants of Great-Grandma Ruby, the proud matriarch of a wonderful family. Let’s say we know that Ruth is a great-grandchild of Ruby, and we want to find Ruth in the graph.

Now, here’s the thing. If we used breadth-first search, we’d end up traversing all of Ruby’s children and grandchildren before reaching even the first great-grandchild.

However, if we use depth-first search, we’d move down the graph right away, reaching the first great-grandchild in just a few steps. While it’s possible that we’d have to traverse the entire graph before finding Ruth, we at least have a shot at finding her quickly. With breadth-first search, though, we have no choice but to traverse all the non–great-grandchildren before we can start inspecting the great-grandchildren.

The question to always ask, then, is do we want to stay close to the starting vertex during our search, or do we specifically want to move far away. Breadth-first search is good for staying close, and depth-first search is ideal for moving far away quickly.