Explore Courses

# What is BFS Algorithm? Breath First Search Algorithm Explained

Updated on 12 October, 2023

3.76K+ views

BFS is a graph traversal technique to explore and analyse graphs. It systematically visits all the neighbouring vertices of a current vertex before moving on to the next level of vertices.

## Understanding Graph Traversal Algorithm in Data Structure

Graph traversal algorithms in data structures are essential techniques for systematically visiting and exploring each node or vertex within a graph. They play a crucial role in understanding the relationships and connectivity present in complex data structures.

Graph traversal algorithms facilitate the examination of graphs by navigating through their nodes in a specific order.

Graph traversal algorithms are widely used in network analysis, routing algorithms, and web crawling, among other fields. They empower efficient analysis and ease the decision-making processes.

The two main approaches for graph traversal are:

Unlike BFS, DFS explores a graph by traversing as far as possible along each branch before backtracking.

## What is Breadth First Search Algorithm?

BFS algorithm starts from a given source vertex and explores the graph layer by layer, examining all the vertices at the same level before descending further. It uses a queue data structure to maintain the order of exploration, ensuring that vertices are visited in a breadth first manner.

## Understanding How BFS Algorithm Works

To implement BFS, a queue data structure is used to maintain the exploration order. The algorithm begins by enqueuing the source vertex and marking it as visited. Then, while the queue is not empty, it dequeues a vertex, visits its adjacent unvisited vertices, enqueues them, and marks them as visited.

This process continues until all vertices have been visited or until the desired condition is met. Using this approach, BFS guarantees that vertices in the BFS graph are visited in order of their distance from the source vertex.

## Need for the Breadth First Search Algorithm

There are several reasons why using the BFS algorithm is essential:

1. Shortest Path Finding: BFS guarantees the shortest path between two vertices in an unweighted graph, making it an ideal choice for route planning or navigation systems.
2. Completeness: BFS is complete for finite graphs, ensuring it explores the entire graph and visits all reachable vertices.
3. Breadth-First Traversal: BFS explores vertices at the same level before moving to deeper levels, providing a breadth-first exploration of the graph.
4. Minimal Memory Usage: BFS uses minimal memory compared to other graph traversal algorithms like DFS, as it only needs to store vertices in the queue.
5. Optimal Solution and Accuracy: In unweighted graphs, BFS ensures that the first occurrence of a target vertex will yield the shortest path, making it efficient for searching tasks.

Programmers often use breadth first search Python for various applications in graph theory and data structures.

Gain an in-depth understanding of graph traversal algorithms and their structures with an MS in Full Stack AI and ML course.

## BFS Algorithm Rules

Some important rules to remember when implementing the breadth first search algorithm for graph traversal:

1. Queue: Use a queue data structure to keep track of the vertices to be visited in the breadth first traversal.
2. Visited Marking: Maintain a visited array or set to keep track of the vertices that have been visited during the traversal.
3. Enqueue and Mark: Enqueue the starting vertex into the queue and mark it as visited.
4. Dequeue and Visit Neighbors: While the queue is not empty, dequeue a vertex, visit it, and enqueue its unvisited neighbouring vertices.
5. Order of Visit: Visit the vertices in the order they were enqueued, ensuring a breadth-first exploration.
6. Avoid Revisiting: Check if a vertex has already been visited before enqueueing it to avoid revisiting vertices.
7. Termination: Terminate the algorithm when the queue becomes empty, indicating that all reachable vertices have been visited.
8. Shortest Path: If finding the shortest path, track the parent of each vertex to reconstruct the path once the destination is reached.

## BFS Algorithm Architecture

The architecture of the BFS algorithm is broken down below:

1. Queue: The BFS algorithm uses a queue data structure to maintain an orderly process when exploring vertex positions. The queue follows the First-In, First-Out (FIFO) principle to ensure that vertices are processed in their order of arrival in the queue.
2. Visited Array or Set: A visited array or set tracks the vertices visited during BFS traversal and ensures that each vertex is processed only once. It ensures no revisited vertices occur while processing each vertex correctly only once.
3. BFS Tree: As the BFS algorithm explores the graph, it constructs a BFS tree. The BFS tree represents the traversal path and reveals the hierarchical relationships between vertices. Each vertex in the tree has its parent, the vertex discovered during the traversal.
4. Enqueue and Mark: The BFS algorithm starts by enqueueing the source vertex into the queue and marking it as visited.
5. Dequeue and Visit Neighbours: While the queue is not empty, the algorithm dequeues a vertex, visits it, and explores its neighbouring vertices. Each unvisited neighbour is enqueued into the queue and marked as visited.
6. Termination: The BFS algorithm terminates when the queue becomes empty. This indicates that all reachable vertices have been visited and processed.

Enrol for the Machine Learning Course from the World’s top Universities. Earn Master, Executive PGP, or Advanced Certificate Programs to fast-track your career.

``````BFS(graph, start_vertex):

queue = create an empty queue

visited = create an empty set or array to track visited vertices

enqueue start_vertex into the queue

while queue is not empty:

current_vertex = dequeue from the queue

process(current_vertex) // e.g., print or perform operations on the current_vertex

for each neighbour in graph[current_vertex]:

if neighbour is not in visited:

enqueue neighbour into the queue

The BFS algorithm starts by initialising an empty queue and an empty set/array to track visited vertices. It begins the traversal from the start_vertex, which is enqueued into the queue and marked as visited.

The algorithm then enters a while loop that continues as long as its queue remains nonempty. At each iteration, a vertex at the front of its queue (denoted by current_vertex) is removed and processed, either through operations on it or printing it out.

Next, the algorithm explores all the neighbours of the current_vertex. For each unvisited neighbour, it enqueues the neighbour into the queue and marks it as visited.

The process continues until the queue becomes empty, indicating that all reachable vertices from the start_vertex have been visited.

You can also check out our free courses offered by upGrad in Management, Data Science, Machine Learning, Digital Marketing, and Technology. All of these courses have top-notch learning resources, weekly live lectures, industry assignments, and a certificate of course completion – all free of cost!

## BFS Algorithm Example

Let’s consider the following graph to understand a BFS example:

A––B
|       |
C––D

We want to perform a breadth first search (BFS) traversal from vertex A to visit all the vertices.

Step 1:

• Enqueue vertex A into the queue.
• Mark A as visited.
• Queue: [A]
• Visited: {A}

Step 2:

• Dequeue A from the queue and process it (e.g., print or perform operations).
• Enqueue its neighbours, B and C, into the queue (as they have yet to be visited).
• Mark B and C as visited.
• Queue: [B, C]
• Visited: {A, B, C}

Step 3:

• Dequeue B from the queue and process it.
• Enqueue its neighbour D into the queue (as it is not visited yet).
• Mark D as visited.
• Queue: [C, D]
• Visited: {A, B, C, D}

Step 4:

• Dequeue C from the queue and process it.
• There are no unvisited neighbours of C, so no vertices are enqueued.
• Queue: [D]
• Visited: {A, B, C, D}

Step 5:

• Dequeue D from the queue and process it.
• There are no unvisited neighbours of D, so no vertices are enqueued.
• Queue: []
• Visited: {A, B, C, D}

The BFS algorithm has now traversed all vertices reachable from the starting vertex A in a breadth-first manner. The order of traversal is A, B, C, and D.

## Complexities Associated With Breadth First Search Algorithm

The complexity of the breadth first search algorithm can be analysed in terms of time and space complexity.

### 1.Time Complexity

BFS has an O(V + E) time complexity, where V represents the number of nodes (vertices) in the graph, and E represents its edges. When dequeuing from its queue or exploring its adjacent vertices, BFS attempts to visit all nodes and edges once. Thus its time complexity increases linearly as more nodes and edges enter or exit it.

### 2. Space Complexity

Space complexity for BFS grows linearly with the number of vertices in a graph (V), represented as an integer value. This is because even under extreme conditions, the BFS queue can simultaneously contain all vertices in its maximum level traversal. Furthermore, its visited array or set requires O(V) space to store visited vertices visited during traversal; hence BFS grows linearly in space complexity with each increase in graph vertex count.

## Breadth First Search Algorithm Code Applications

Here are a few examples of the numerous applications of the BFS algorithm in various domains, showcasing its versatility and usefulness in graph exploration and analysis:

• Shortest Path: BFS can be used to find the shortest path between two vertices in an unweighted graph. The shortest path can be reconstructed by tracking the parent nodes during traversal.
• Connectivity: BFS can determine whether a graph is connected or not. The graph is connected if BFS reaches all vertices from a given source vertex.
• Web Crawling: BFS is widely used in web crawling or web scraping. It helps explore web pages systematically by following links and discovering new pages at each level.
• Social Network Analysis: BFS can help analyse social networks, identify clusters, find the shortest path between users, or calculate measures like degrees of separation.
• Bipartite Graphs: BFS can determine whether a graph is bipartite or not. It can colour the vertices with two different colours such that no two adjacent vertices have the same colour.
• Minimum Spanning Tree: BFS can be used to find the minimum spanning tree (MST) of a connected, weighted graph when all edge weights are equal.
• Puzzle Solving: BFS can solve puzzles like the sliding tile puzzle or the maze problem, finding the shortest path to the goal state.
• Network Routing: BFS is used in network routing algorithms, such as finding the shortest path between routers or determining the best route for data packets.

## Conclusion

The Breadth First Search (BFS) algorithm is an invaluable tool for exploring and analysing graphs in a breadth-first manner. Its efficiency, accuracy in finding the shortest path, and versatility in various applications make it a fundamental technique in data structures and algorithms.

Aspiring IT professionals or software developers looking to enhance their skills and master graph traversal algorithms like DFS and BFS can check out upGrad’s Advanced Certificate Programme in Machine Learning & NLP from IIITB. Put yourself at the forefront of a technologically evolving landscape with upGrad.

### 1. What data structures are used in the BFS algorithm?

The breadth first search algorithm uses a queue data structure to keep track of the vertices to be visited and a visited array or set to mark visited vertices.

### 2. Can the BFS algorithm be applied to both trees and graphs?

Yes, the BFS algorithm can be applied to both trees and graphs. It explores the nodes/vertices in a breadth-first manner, regardless of the underlying structure.

### 3. How does the BFS algorithm enable the breadth first traversal of a tree or graph?

The BFS algorithm uses a queue to enqueue and dequeue vertices, ensuring that vertices at the same level are visited before moving to the next level.

### 4. Explain the implementation of breadth first search Python.

BFS can be implemented in Python using a queue and a visited set/array. The algorithm follows the steps of enqueuing, dequeuing, and visiting neighbouring vertices.

### 5. What is the difference between BFS and DFS (Depth First Search)?

The main distinction between BFS and DFS lies in their respective traversal orders; BFS explores vertex edges breadth-first, while DFS employs depth-first traversal methods, often employing stacks.

Director of Engineering @ upGrad. Motivated to leverage technology to solve problems. Seasoned leader for startups and fast moving orgs. Working on solving problems of scale and long term technology strategy.

See More

## SUGGESTED BLOGS

11.8K+

How to Compute Square Roots in Python

A high-level, multi-paradigm programming language with an object-oriented approach, Python is designed to be highly extensible, with multiple compact modules, including a multi-functional math module.  Here, we explore the different ways in which Python can calculate a very specific mathematical functionality – square roots – with or without the use of its math and cmath modules. Enroll for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career. What is a Square Root? While most of us are familiar with this mathematical concept, it’s worth refreshing our memory with a simple definition: The value ‘y’ is x’s square root because ‘y’, when multiplied by itself, yields the original number x. In mathematical terms this may be expressed as follows: If x = y x y or x = y2 then √x = y Square Root Functionality in Python A number’s square root may be extricated using Python in a variety of different ways: 1. Using the Python math module: A. With the inbuilt math.sqrt( ) function: Step 1: Import the math module Step 2: Use the sqrt( ) function Input code: Import math Print(“54’s square root is” ,math.sqrt(49)) Output: 54’s square root is 7.348469228349534 B. With the inbuilt math.pow( ) function: Step 1: Import the math module Step 2: Use the pow( ) function This operates on the simple mathematical principle: √x = x1/2  or  √x = x0.5. The function requires the input of two parameters – the base number and its exponent. Input code: Import math number = float(input(” Please Enter any numeric Value : “)) squareRoot = math.pow(number, 0.5) print(“The given number {0}’s square root = {1}”.format(number, squareRoot)) Output: Please Enter any numeric Value: 54 The Given Number 54.0’s square root = 7.348469228349534 Check out upGrad’s Advanced Certification in DevOps  Best Machine Learning and AI Courses Online Master of Science in Machine Learning & AI from LJMU Executive Post Graduate Programme in Machine Learning & AI from IIITB Advanced Certificate Programme in Machine Learning & NLP from IIITB Advanced Certificate Programme in Machine Learning & Deep Learning from IIITB Executive Post Graduate Program in Data Science & Machine Learning from University of Maryland To Explore all our courses, visit our page below. Machine Learning Courses 2. Using the Python cmath module Step 1: Import the complex math (cmath) module Step 2: Use the cmath.sqrt( ) function The cmath module helps compute the  square root of real or complex numbers. Input code: import cmath num = 1+2j sqrt = cmath.sqrt(num) print(‘{0}’s square root is {1:0.2f} + {2:0.2f}’ .format(num,sqrt.real,sqrt.imag)) Output: (1+2j)’s square root is 1.27+0.79 In-demand Machine Learning Skills Artificial Intelligence Courses Tableau Courses NLP Courses Deep Learning Courses   3. Using the exponent ** operator: Operates on the same principle as the pow( ) function, i.e. √x = x1/2  or  √x = x0.5 but does not require users to import the math module Input code: def sqrt(n): if n < 0: Return Else: return n**0.5 print(sqrt(54)) Output: 7.348469228349534 Popular AI and ML Blogs & Free Courses IoT: History, Present & Future Machine Learning Tutorial: Learn ML What is Algorithm? Simple & Easy Robotics Engineer Salary in India : All Roles A Day in the Life of a Machine Learning Engineer: What do they do? What is IoT (Internet of Things) Permutation vs Combination: Difference between Permutation and Combination Top 7 Trends in Artificial Intelligence & Machine Learning Machine Learning with R: Everything You Need to Know AI & ML Free Courses Introduction to NLP Fundamentals of Deep Learning of Neural Networks Linear Regression: Step by Step Guide Artificial Intelligence in the Real World Introduction to Tableau Case Study using Python, SQL and Tableau At upGrad, our Advanced Certificate in Machine Learning and Deep Learning, offered in collaboration with IIIT-B, is an 8-month course taught by industry experts to give you a real-world idea of how deep learning and machine learning work. In this course, you’ll get a chance to learn important concepts around machine learning, deep learning, computer vision, cloud, neural networks, and more.  Check out the course page and get yourself enrolled soon!
02 Feb'23

6.17K+

Machine Learning for Java Developers

19 Feb'23

5.36K+

Maths for Machine Learning Specialisation

20 Feb'23

5.29K+

Machine Learning vs Data Analytics: A Brief Comparison

20 Feb'23

5.51K+

CPU vs GPU in Machine Learning? Which is Important

24 Feb'23

3.57K+

What is BFS Algorithm? Breath First Search Algorithm Explained

27 Jul'23

SUPPORT

MBA

DATA SCIENCE & ANALYTICS

DOCTORATE

SOFTWARE & TECH

AI & ML

MARKETING

MANAGEMENT

LAW