Breadth-First Search (BFS) Algorithm With Python

Understanding of BFS graph search algorithm with Python implementation.

In Computer Science, traversing or searching a graph means visiting or processing each node of the graph. There are various algorithms for graph traversal. Breadth-first search is one of them. It is one of the most fundamental graph search techniques.

In this article, we will dive into the basics of breadth-first search, learn how the algorithm works, and see how to implement it with Python.

The Basics of BFS

To understand BFS, I find the intro from the article Breaking Down Breadth-First Search by Vaidehi Joshi helpful —

When it comes to learning, there are generally two approaches one can take: you can either go wide, and try to cover as much of the spectrum of a field as possible, or you can go deep, and try to get really, really specific with the topic that you’re learning.

To traverse a graph, we can also take two approaches. We can go wide and traverse the graph level by level, or we can go deep and traverse a branch as far as possible.

BFS goes wide. That means we traverse a graph level by level. We take a node, traverse all of its child nodes, and then move to another node. Because all of the child nodes of a node are on the same level.

Now let's understand BFS more thoroughly by visualizing each step of the algorithm using this graph:

To understand the level-wise searching of BFS, I am using a tree as an example. But don’t worry. A tree is a special kind of graph just without any cycle.

Note: It’s easy to think ‘parent node’ and ‘child node’ relationship in a tree. But graphs that contain cycles, we will think of directly connected nodes as ‘neighbor nodes’. We will get to that soon.

We can divide this graph into three levels:

Let’s see how the level-wise traversing works in this graph considering ‘A’ as the root node:

This traversal technique is easy to understand for us humans. But we need to think about how a computer can understand it.

The Queue data structure can help us with this.

Queue for Level-Wise Search

Queue is a linear structure of data that follows the First-In-First-Out (FIFO) principle. The element entering first in a queue will also leave first.

You can read these articles to know more about queues and how to implement them:

The FIFO principle of a queue will ensure the level-wise searching of BFS. Let’s see how from the sketch below:

We start from a root/source node, push it to the queue, and continue traversing the rest. These are the overall steps of BFS:

1. Start with a root node and push it to the queue.
2. Mark the root node as visited and print it
3. Continue a loop until the queue is empty:
   3.1. Pop the front node from the queue
   3.2. Push the child/neighbor nodes of the front node to the queue
   3.3  Mark them as visited and print

Here we are marking a node as ‘visited’ while pushing it to the queue. Because we don’t want to traverse the same node twice.

A Bit Complex Example

Now we will see a little bit complex graph that contains cycles in it.

We can’t determine child nodes of a node in an undirected graph that contains cycles. Rather we will use the concept of ‘neighbor nodes’ here. The nodes directly connected to a node are the neighbors of that node.

This graph shows us why we need to check already visited nodes. We do it to avoid traversing the same node more than once.

Now that we understand how BFS works using a queue data structure, it's time to see the python implementation of BFS.

Coding the BFS Algorithm With Python

To apply BFS to a graph, we need to represent the graph in our code first. We will use the adjacency list representation of a graph.

The adjacency list of the graph above is like this:

You can learn about different graph representations and how to represent a graph using Python from this reading:

Now it's time to code the algorithm.

Here we are using a simple Python list as our queue. But you may implement your own queue class or use some more efficient modules for later use.

The above code will generate the following output where ‘A’ is the root node:

BFS: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]

If we choose ‘C’ as the root node, we will get this output:

BFS: [‘C’, ‘A’, ‘D’, ‘B’, ‘E’]

And that's it! We’ve implemented the BFS algorithm using Python.

Conclusion

In this article, we learned about an important graph searching algorithm. We saw how the BFS algorithm works in detail. We also learned to code the algorithm using Python.

There is a lot to explore on the topic of graphs and graph traversals. But first, you need to study the basic algorithms and understand how they work. This will help you build a solid foundation on graphs.

I hope from this article you get a good understanding of the BFS algorithm and graph traversal in general. Thanks for reading.

Helpful Resources

If you enjoy reading articles like these, consider becoming a Medium member. That gives you unlimited access to all stories on Medium. If you sign up using my referral link below, I’ll earn a small commission from your $5 monthly fees. This way you can support me as a writer.