Graph Algorithms : Breadth First Search

In the previous post on graph algorithms, we discussed the depth first search algorithm in detail. Check it out here. Today we will discuss the breadth first search algorithm and implement it in Python. Let’s get started.

Breadth First Search

Breadth first search is a graph traversal and search algorithms that explores the nodes/vertices in a graph level by level i.e explores all the neighboring/sibling nodes of a vertex first. See the example below :

BFS Example

Let’s implement our graph in python as shown below

Simple Graph

Again we will be using an adjacency list to perform BFS. The steps to perform breadth first search are as follows :

1. Maintain a list of visited nodes/vertices in the graph
2. Pick a starting vertex. If the vertex has not been visited, add it to the visited list. Now, enqueue it into a queue.
3. Dequeue the node and enqueue all the neighboring nodes to the queue.
4. Repeat steps 2 and 3 until the queue is empty.

BFS using queue

The complexity of the BFS algorithm on an adjacency list is O(V+E) when used on an adjacency list. To check out an implementation of BFS using a matrix (O(V²) complexity) refer to this link.

Applications

Breadth-First Search is used in Peer-to-Peer network applications such as communication and file-sharing (eg. BitTorrent) to find all the neighboring nodes in a network. It is also used for broadcasting information (packets of information) in a network of nodes.

References

1. https://www.javatpoint.com/breadth-first-search-algorithm
2. https://www.techiedelight.com/breadth-first-search/
3. https://jovian.ai/aakashns/python-graph-algorithms