Breadth-First Search (BFS) is a fundamental algorithm for searching or traversing tree and graph data structures.
The algorithm works as below:
- Select a node (the 'root' in a tree, or any node in a graph)
- Visit all of the neighbor nodes at the current depth before moving on to nodes at the next depth level.
In rush? Go to the full code for the Python BFS implementation.
BFS is useful to find the shortest path of an unweighted graph.
In this tutorial, I will show you how to implement the BFS algorithm in Python the easy way. Keep reading!
Table of Contents
Follow the steps below to implement the BFS algorithm in Python.
Before we dive into the BFS algorithm, we need a graph to work with. I will use the graph as the one shown in the visualization above.
For simplicity, we'll use an adjacency list to represent a graph, where each node maps to a list of its neighbors.
The BFS algorithm pseudo code can be described as follows:
- Start by putting any vertex at the back of a queue.
- Take the front vertex of the queue, add it to the visited list.
- For each vertex which is a neighbor of the front vertex and not visited, continue adding it to the back of the queue.
- Keep repeating steps 2 and 3 until the queue is empty.
Common BFS implementation uses a queue to store the nodes to be visited. So I will use
deque (pronounced as DECK) from the
collections module to implement the queue for efficient
Let's implement the BFS algorithm in Python.
Let's test the
bfs function with the graph we defined earlier. Here is the full code.
You can run this code by using the command:
The output would be:
This output represents the order in which the nodes are visited when starting the BFS from node 'A'.
In this tutorial, we have learned how to implement the BFS algorithm in Python using a queue.
I know algorithm is hard to learn, but this is one of the most easiest algorithms. So read it again if you don't understand it the first time.