How to Implement Breadth-First Search

Breadth-first search (BFS) is an algorithm used for traversing graph data structures. In other words, BFS implements a specific strategy for visiting all the nodes (vertices) of a graph – more on graphs in a while. What is this exploration strategy? It’s very simple and effective. BFS starts with a node, then it checks the neighbors of the initial node, then the neighbors of the neighbors, and so on. In case you didn’t recall it, two vertices are ‘neighbors’ if they are connected with an edge.

BFS is an AI search algorithm, that can be used for finding solutions to a problem. Indeed, several AI problems can be solved by searching through a great number of solutions. The reasoning process, in these cases, can be reduced to performing a search in a problem space. For instance, solving the Rubik’s Cube can be viewed as searching for a path that leads from an initial state, where the cube is a mess of colors, to the goal state, in which each side of the cube has a single color. The solution path is a sequence of (admissible) moves.Goal state for the Rubik’s Cube.

The trick here is to be able to represent the Rubik’s Cube problem as a graph, where the nodes correspond to possible states of the cube and the edges correspond to possible actions (e.g., rotate left/right, up/down). If we can formalise the problem like a graph, then we can use BFS to search for a solution (at least theoretically, given that the Rubik’s Cube problem is intractable for BFS in terms of memory storage). That’s why BFS is considered to be an AI search algorithm.

In this tutorial, I won’t get into the details of how to represent a problem as a graph – I’ll certainly do that in a future post. The main goal for this article is to explain how breadth-first search works and how to implement this algorithm in Python. In particular, in this tutorial I will:

Provide a way of implementing graphs in Python.
Explain how BFS works and outline its advantages/disadvantages.
Provide an implementation of breadth-first search to traverse a graph.
Return the shortest path between two nodes of a graph using BFS, with the distance measured in number of edges that separate two vertices.

If you’re only interested in the implementation of BFS and want to skip the explanations, just go to this GitHub repo and download the code for the tutorial.

As you might have understood by now, BFS is inherently tied with the concept of a graph. So, let’s see how we can implement graphs in Python first.

The graph data structure

For the sake of this tutorial, I’ve created a connected graph with 7 nodes and 7 edges. The edges are undirected and unweighted. Distance between two nodes will be measured based on the number of edges separating two vertices.Sample graph used for this tutorial.

It is possible to represent a graph in a couple of ways: with an adjacency matrix (that can be implemented as a 2-dimensional list and that is useful for dense graphs) or with an adjacency list (useful for sparse graphs). In this tutorial, I use the adjacency list. An effective/elegant method for implementing adjacency lists in Python is using dictionaries. The keys of the dictionary represent nodes, the values have a list of neighbors.

# sample graph implemented as a dictionary
graph = {'A': ['B', 'C', 'E'],
         'B': ['A','D', 'E'],
         'C': ['A', 'F', 'G'],
         'D': ['B'],
         'E': ['A', 'B','D'],
         'F': ['C'],
         'G': ['C']}

For example, the first element of the dictionary above tells us that node ‘A’ is connected with node ‘B’, ‘C’ and ‘E’, as is clear from the visualisation of the sample graph above.

Now that you know how to implement graphs in Python, it’s time to understand how BFS works before implementing it.

The intuition behind BFS

BFS visits all the nodes of a graph (connected component) following a breadthward motion. In other words, BFS starts from a node, then it checks all the nodes at distance one from the starting node, then it checks all the nodes at distance two and so on. In order to remember the nodes to be visited, BFS uses a queue. The algorithm can keep track of the vertices it has already checked to avoid revisiting them, in case a graph had one or more cycles.

In particular, BFS follows the following steps:

Check the starting node and add its neighbors to the queue.
Mark the starting node as explored.
Get the first node from the queue / remove it from the queue
Check if node has already been visited.
If not, go through the neighbors of the node.
Add the neighbor nodes to the queue.
Mark the node as explored.
Loop through steps 3 to 7 until the queue is empty.

To implement the BFS queue a FIFO (First In, First Out) is used. In FIFO queues, the oldest (first) entry is processed first. The process is similar to what happens in queues at the post office. Who arrives first is served first.Example of a FIFO queue.

How would BFS traverse our sample graph in case the starting node was ‘A’? The answer is pretty simple. First, BFS would check all of the nodes at distance 1 from ‘A’ (‘B’, ‘E’ and ‘C’). Then, it would visit all of the nodes at distance 2 (‘D’, ‘F’ and ‘G’).

Looking at the image below, it’s now clear why we said that BFS follows a breadthward motion. The algorithm checks all the nodes at a given depth (distance from the entry point), before moving to the level below.The numbers in red indicate the order in which BFS visits the nodes of the graph.

Traversing a graph

Visiting all the nodes of a connected component with BFS, is as simple as implementing the steps of the algorithm I’ve outlined in the previous section.

Let’s start off by initialising a couple of lists that will be necessary to maintain information about the nodes visited and yet to be checked.

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
    # keep track of all visited nodes
    explored = []
    # keep track of nodes to be checked
    queue = [start]

As you can note, queue already has a node to be checked, i.e., the starting vertex that is used as an entry point to explore the graph.

The next step is to implement a loop that keeps cycling until queue is empty. At each iteration of the loop, a node is checked. If this wasn’t visited already, its neighbors are added to queue.

# visits all the nodes of a graph (connected component) using BFS
def bfs_connected_component(graph, start):
    # keep track of all visited nodes
    explored = []
    # keep track of nodes to be checked
    queue = [start]
 
    # keep looping until there are nodes still to be checked
    while queue:
        # pop shallowest node (first node) from queue
        node = queue.pop(0)
        if node not in explored:
            # add node to list of checked nodes
            explored.append(node)
            neighbours = graph[node]
 
            # add neighbours of node to queue
            for neighbour in neighbours:
                queue.append(neighbour)
    return explored
 
bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G']

Tip: To make the code more efficient, you can use the deque object from the collections module instead of a list, for implementing queue. This way you can use the popleft() method instead of the pop(0) built-in function on queue. This will result in a quicker code as popleft()has a time complexity of O(1) while pop(0) has O(n).

Once the while loop is exited, the function returns all of the visited nodes.

That’s it! We have a functioning BFS implementation that traverses a graph. Now on to a more challenging task: finding the shortest path between two nodes.

Identifying the shortest path between two nodes of a graph

For this task, the function we implement should be able to accept as argument a graph, a starting node (e.g., ‘G’) and a node goal (e.g., ‘D’). If the algorithm is able to connect the start and the goal nodes, it has to return the path. The nice thing about BFS is that it always returns the shortest path, even if there is more than one path that links two vertices.

There are a couple of main differences between the implementations of BDF for traversing a graph and for finding the shortest path. First, in case of the shortest path application, we need for the queue to keep track of possible paths (implemented as list of nodes) instead of nodes. Second, when the algorithm checks for a neighbor node, it needs to check whether the neighbor node corresponds to the goal node. If that’s the case, we have a solution and there’s no need to keep exploring the graph.

# finds shortest path between 2 nodes of a graph using BFS
def bfs_shortest_path(graph, start, goal):
    # keep track of explored nodes
    explored = []
    # keep track of all the paths to be checked
    queue = [[start]]
 
    # return path if start is goal
    if start == goal:
        return "That was easy! Start = goal"
 
    # keeps looping until all possible paths have been checked
    while queue:
        # pop the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        if node not in explored:
            neighbours = graph[node]
            # go through all neighbour nodes, construct a new path and
            # push it into the queue
            for neighbour in neighbours:
                new_path = list(path)
                new_path.append(neighbour)
                queue.append(new_path)
                # return path if neighbour is goal
                if neighbour == goal:
                    return new_path
 
            # mark node as explored
            explored.append(node)
 
    # in case there's no path between the 2 nodes
    return "So sorry, but a connecting path doesn't exist :("
 
bfs_shortest_path(graph, 'G', 'D')  # returns ['G', 'C', 'A', 'B', 'D']

Congrats! You’ve now implemented BFS for traversing graphs and for finding the shortest path between two nodes. Now, let’s have a look at the advantages/disadvantages of this search algorithm..

The good and the bad of BFS

There’s a great news about BFS: it’s complete. That’s because this algorithm is always able to find a solution to a problem, if there is one. For example, if a path exists that connects two nodes in a graph, BFS will always be capable of identifying it – given the search space is finite.

Completeness is a nice-to-have feature for an algorithm, but in case of BFS it comes to a high cost. The execution time of BFS is fairly slow, because the time complexity of the algorithm is exponential. What’s worse is the memory requirements. That’s because BFS has to keep track of all of the nodes it explores. In the case of problems which translate into huge graphs, the high memory requirements make the use of BFS unfeasible. For example, to solve the Rubik’s Cube with BFS we need c. 10 zettabytes (1021 bytes)of RAM, which, the last time I checked, is not yet available on our laptops!

Lesson learned: You should use BFS only for relatively small problems.

What can you use BFS for?

Even though BFS is not the best option for problems involving large graphs, it can be successfully employed for a number of applications. I’ll list just a few of them to give you an idea:

Shortest path of unweighted graphs (we did this already – hooray!).
Discover all nodes reachable from an initial vertex (we did this too!)
Find neighbor nodes in peer to peer networks like BitTorrent.
Used by crawlers in search engines to visit links on a webpage, and keep doing the same recursively.
Find people at a given distance from a person in social networks.
Identify all neighbor locations in GPS systems.
Search whether there’s a path between two nodes of a graph (path finding).
Allow broadcasted packets to reach all nodes of a network.

Conclusion

Breadth-first search is an algorithm used to traverse and search a graph. If you’ve followed the tutorial all the way down here, you should now be able to develop a Python implementation of BFS for traversing a connected component and for finding the shortest path between two nodes.

There are a few takeaway messages I’d like you to remember from this tutorial:

Graphs are the data structure of election to search for solutions in complex problems.
BFS explores nodes one depth level at a time. It starts from a node, then checks the neighbors of the initial node, then the neighbors of the neighbors and so on…
BFS is complete, in that it always returns a solution in case there is one.
BFS is often impracticable in large real-world problems, because of excessive memory requirements.

Useful resources

PreviousTraverse A Tree NextBreadth First Search

Last updated 5 years ago