Breadth First Search In Python

Breadth First Search In Python

Breadth First Search (or BFS for short) is a graph traversal algorithm. In BFS, we visit all of the neighboring nodes at the present depth prior to moving on to the nodes at the next depth.

Breadth First Search Meaning

Breadth First Search is best explained by comparing it with its opposite (i.e. Depth First Search). Suppose we had the following graph.

We begin by visiting node 2.

This is the point where the two algorithms differ. In Depth First Search, we continue down the branch and visit node 4.

In contrast, in Breadth First Search, we visit node 3 (i.e. the other node at a depth of 1).

Breadth First Search Algorithm

To implement the BFS algorithm, we make use a of queue to keep track of the nodes we have yet to visit. Suppose we had the following graph.

We start off by visiting node 0 and add all of its neighbours to the queue. It’s important to note that the order in which the nodes are added to the queue is completely arbitrary. We could just as well have added node 3 before node 1.

In the subsequent iteration of the algorithm, we visit the next element in the queue (i.e. node 1) and add of its neighbours. It should be pointed out that since we’ve already visited node 0 and node 3 is already in the queue, we don’t add them again.

We visit node 3 and add node 4 to the queue given that it wasn’t already present.

All that remains is to visit the nodes in the order that they appear in the queue.

Python Example

We start off by importing the libraries necessary to plot the graph.

import networkx as nx  
from matplotlib import pyplot as plt  
plt.rcParams["figure.figsize"] = (10,10)

We randomly generate a graph with 7 nodes where the probability that we create an edge connecting two nodes is 40%.

G = nx.random_graphs.fast_gnp_random_graph(7, 0.4)

We define and call a function that plots the various components of the graph.

def draw_graph(G):  
    pos = nx.spring_layout(G)  
    nx.draw_networkx_nodes(G, pos, node_size=500, alpha=0.5)  
    nx.draw_networkx_labels(G, pos)  
    nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)

draw_graph(G)

We can list the nodes and edges in the graph as follows.

G.nodes

Next, we implement the Breadth First Search algorithm. In order to determine the nodes that are adjacent to the current node, we find all the tuples containing the current node, and add the other node.

def bfs(graph, starting_node):  
    visited = []  
    queue = [starting_node]  
      
    while queue:  
        node = queue.pop(0)  
        if node not in visited:  
            visited.append(node)              
            for edge in graph.edges:  
                if edge[0] == node:  
                    queue.append(edge[1])  
                elif edge[1] == node:  
                    queue.append(edge[0])  
    return visited

We call the function using the graph we just created and node 1 as the starting node.

bfs(G, 1)

As we expect, the 1st and 2nd nodes in the list are 0 and 5 which are adjacent to 1.

Shortest Path

Let’s see how we can use the Breadth First Search algorithm to determine the shortest path between two nodes.

We define a function similar to the previous one, only this time around, we take an additional argument for the node we want to find a path to. We queue the paths to the various nodes in the graph as opposed to the nodes themselves. We know that the last node in the path is the last node we visited. Therefore, we iterate over all of its neighbours, and create a new path consisting of the path that led up to the current node plus the edge connecting it to its neighbour. If one of the neighbouring nodes is our goal, then we’re done and return new the path. Otherwise, we continue to iterate over the remaining paths in the queue.

def find_shortest_path(graph, starting_node, goal):  
    visited = []  
    queue = [[starting_node]]  
      
    while queue:  
        path = queue.pop(0)  
        node = path[-1]  
        if node not in visited:  
            neighbours = []  
            for edge in graph.edges:  
                if edge[0] == node:  
                    neighbours.append(edge[1])  
                elif edge[1] == node:  
                    neighbours.append(edge[0])  
            for neighbour in neighbours:  
                new_path = list(path)  
                new_path.append(neighbour)  
                queue.append(new_path)  
                  
                if neighbour == goal:  
                    return new_path  
              
            visited.append(node)  
              
    return []

We find the shortest path from node 1 to node 3.

find_shortest_path(G, 1, 3)

As we can see, the algorithm correctly determined the shortest path between the nodes.