Implementing Breadth First Search with Python

Introduction

Breadth First Search or BFS is a Search technique (Uninformed Search) that is applied on Graphs and Tress to search a specific node item. In data structure, there is one more search algorithm called Depth First Search which comes in a similar category but BFS (Breath First Search) is used widely for its optimal performance.

In this tutorial, we will implement Breadth First Search Algorithm in Python Language. Here, we will apply this search technique to graphs and trees both to understand the fundamentals more deeply. So before we start writing our code, let's get a brief knowledge of how actually BFS algorithm works through an example.

👉Visit Also: Implementing Depth First Search with Python 

How BFS (Breadth First Search) works?

Let's try to understand how the BFS algorithm does work through diagrams (see below). To know it better, we will use a Tree here.

BFS starts traverse from the root node (for the case of trees only; for graphs, it can be any node chosen by the user) and then the connecting child nodes level-wise (shallowest node). In each traversal, it stored the value of the node in a Queue. Since Queue works in FIFO (First in first out) style, it fetches the first present node item from there and tries to find if there are any successor nodes connected with that parent node. If yes, then the algorithm traverse and stores the node item into the queue in the same way. This cycle goes on until the algorithm finds the desired node item and returns the shortest path of that node from the root or starting node.

The reason we recognize the algorithm optimal than DFS (Depth First Search) is that it uses Queue to manage the node items and traverse a tree level-wise instead of digging deep as per the height of the tree. It makes it more convenient and surety to search an element from a tree or graphs than DFS.

Let's try to understand the logic of traversal through the below diagrams. Here, we have a single Tree having two levels and six nodes with six data items.

Traverse A

Traverse B

Traverse C

Traverse D

Traverse E

Traverse F

I hope you guys got an idea of how BFS works actually. Here, if we try to find the optimal path between the root node 'A' and node 'E', it would be "A-B-E". This is how Breadth First Search is used to find the optimal path between two nodes (In Artificial Intelligence).

Let's move on to the next topic. Now we will implement the algorithm using python programming.

The Program

The below program will work for both Graphs and Trees (But we are taking the example of the tree here). There, we declared an extra set variable ('visited') to track if the present node is visited already or not.

It will be very helpful when a single node is getting multiple paths to reach from different nodes (In the case of Graphs, see the image above).

# A Python Program to Perform Breadth First Search 

# The given tree or graph
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

# Python set stores only identical value
visited = set()
queue = []

def BFS(graph, visited, node):
    # Adding the first node
    visited.add(node)
    queue.append(node)
    
    # Iterate through each item of the queue
    while queue:
        poppedItem = queue.pop(0)
        print(poppedItem, end=" ")

        # Iterate through each item of the list value of each key of the
        # graph dictionary
        for neighbor in graph[poppedItem]:
            if neighbor not in  visited:
                visited.add(neighbor)
                queue.append(neighbor)
    print("\n")

if __name__ == "__main__":
    # Calling the BFS function
    BFS(graph, visited, 'A')

Output

A B C D E F 

Complexity Analysis

In Data Structure, the complexity will stand like the following.

Time Complexity: O(V+E) where V is the number of vertices or nodes, and E is the number of edges.

Space Complexity: O(V)

In Artificial Intelligence, the time complexity stands like this,

Time Complexity: O(b^d) where b is the branch factor (max. child node of a parent node), and d is the depth. Let's understand it better.

If I take the above Tree example, the depth of the Tree is 2 and a single node have a maximum of 2 child node which is the branch factor.

So, if I try to find the node 'E', the time complexity would be O(2^2) = O(4) [where, b=2, d=2]. It means, The program will take a maximum of 4 searches to find node 'E'.

Summary

In this tutorial, our topic of discussion was the Breadth First Search algorithm, how it works, and the implementation of the algorithm using Python Programming. We made a single program for both Graphs and Trees to work with.

In closing, we discussed the time and space complexity of the algorithms. I hope now you can create a discussion on the Breadth First Search algorithm easily.

Task for you

Try to traverse the graph example using the same python program and tell me what you get. 

If you have any doubts related to this topic, let me know in the comment section. You will get a reply soon.

Thanks for reading!

PySeek