Explore Courses
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Birla Institute of Management Technology Birla Institute of Management Technology Post Graduate Diploma in Management (BIMTECH)
  • 24 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Popular
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science & AI (Executive)
  • 12 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
University of MarylandIIIT BangalorePost Graduate Certificate in Data Science & AI (Executive)
  • 8-8.5 Months
upGradupGradData Science Bootcamp with AI
  • 6 months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
OP Jindal Global UniversityOP Jindal Global UniversityMaster of Design in User Experience Design
  • 12 Months
Popular
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Rushford, GenevaRushford Business SchoolDBA Doctorate in Technology (Computer Science)
  • 36 Months
IIIT BangaloreIIIT BangaloreCloud Computing and DevOps Program (Executive)
  • 8 Months
New
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Popular
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
Golden Gate University Golden Gate University Doctor of Business Administration in Digital Leadership
  • 36 Months
New
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
Popular
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
Bestseller
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
IIIT BangaloreIIIT BangalorePost Graduate Certificate in Machine Learning & Deep Learning (Executive)
  • 8 Months
Bestseller
Jindal Global UniversityJindal Global UniversityMaster of Design in User Experience
  • 12 Months
New
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in AI and Emerging Technologies (Blended Learning Program)
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
ESGCI, ParisESGCI, ParisDoctorate of Business Administration (DBA) from ESGCI, Paris
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration From Golden Gate University, San Francisco
  • 36 Months
Rushford Business SchoolRushford Business SchoolDoctor of Business Administration from Rushford Business School, Switzerland)
  • 36 Months
Edgewood CollegeEdgewood CollegeDoctorate of Business Administration from Edgewood College
  • 24 Months
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with Concentration in Generative AI
  • 36 Months
Golden Gate University Golden Gate University DBA in Digital Leadership from Golden Gate University, San Francisco
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA by Liverpool Business School
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA (Master of Business Administration)
  • 15 Months
Popular
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Business Administration (MBA)
  • 12 Months
New
Deakin Business School and Institute of Management Technology, GhaziabadDeakin Business School and IMT, GhaziabadMBA (Master of Business Administration)
  • 12 Months
Liverpool John Moores UniversityLiverpool John Moores UniversityMS in Data Science
  • 18 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityMaster of Science in Artificial Intelligence and Data Science
  • 12 Months
Bestseller
IIIT BangaloreIIIT BangalorePost Graduate Programme in Data Science (Executive)
  • 12 Months
Bestseller
O.P.Jindal Global UniversityO.P.Jindal Global UniversityO.P.Jindal Global University
  • 12 Months
WoolfWoolfMaster of Science in Computer Science
  • 18 Months
New
Liverpool John Moores University Liverpool John Moores University MS in Machine Learning & AI
  • 18 Months
Popular
Golden Gate UniversityGolden Gate UniversityDBA in Emerging Technologies with concentration in Generative AI
  • 3 Years
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (AI/ML)
  • 36 Months
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDBA Specialisation in AI & ML
  • 36 Months
Golden Gate University Golden Gate University Doctor of Business Administration (DBA)
  • 36 Months
Bestseller
Ecole Supérieure de Gestion et Commerce International ParisEcole Supérieure de Gestion et Commerce International ParisDoctorate of Business Administration (DBA)
  • 36 Months
Rushford, GenevaRushford Business SchoolDoctorate of Business Administration (DBA)
  • 36 Months
Liverpool Business SchoolLiverpool Business SchoolMBA with Marketing Concentration
  • 18 Months
Bestseller
Golden Gate UniversityGolden Gate UniversityMBA with Marketing Concentration
  • 15 Months
Popular
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Corporate & Financial Law
  • 12 Months
Bestseller
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Intellectual Property & Technology Law
  • 12 Months
Jindal Global Law SchoolJindal Global Law SchoolLL.M. in Dispute Resolution
  • 12 Months
IIITBIIITBExecutive Program in Generative AI for Leaders
  • 4 Months
New
IIIT BangaloreIIIT BangaloreExecutive Post Graduate Programme in Machine Learning & AI
  • 13 Months
Bestseller
upGradupGradData Science Bootcamp with AI
  • 6 Months
New
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
KnowledgeHut upGradKnowledgeHut upGradSAFe® 6.0 Certified ScrumMaster (SSM) Training
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutCertified ScrumMaster®(CSM) Training
  • 16 Hours
upGrad KnowledgeHutupGrad KnowledgeHutLeading SAFe® 6.0 Certification
  • 16 Hours
KnowledgeHut upGradKnowledgeHut upGradPMP® certification
  • Self-Paced
upGrad KnowledgeHutupGrad KnowledgeHutAWS Solutions Architect Certification
  • 32 Hours
upGrad KnowledgeHutupGrad KnowledgeHutAzure Administrator Certification (AZ-104)
  • 24 Hours
KnowledgeHut upGradKnowledgeHut upGradAWS Cloud Practioner Essentials Certification
  • 1 Week
KnowledgeHut upGradKnowledgeHut upGradAzure Data Engineering Training (DP-203)
  • 1 Week
MICAMICAAdvanced Certificate in Digital Marketing and Communication
  • 6 Months
Bestseller
MICAMICAAdvanced Certificate in Brand Communication Management
  • 5 Months
Popular
IIM KozhikodeIIM KozhikodeProfessional Certification in HR Management and Analytics
  • 6 Months
Bestseller
Duke CEDuke CEPost Graduate Certificate in Product Management
  • 4-8 Months
Bestseller
Loyola Institute of Business Administration (LIBA)Loyola Institute of Business Administration (LIBA)Executive PG Programme in Human Resource Management
  • 11 Months
Popular
Goa Institute of ManagementGoa Institute of ManagementExecutive PG Program in Healthcare Management
  • 11 Months
IMT GhaziabadIMT GhaziabadAdvanced General Management Program
  • 11 Months
Golden Gate UniversityGolden Gate UniversityProfessional Certificate in Global Business Management
  • 6-8 Months
upGradupGradContract Law Certificate Program
  • Self paced
New
IU, GermanyIU, GermanyMaster of Business Administration (90 ECTS)
  • 18 Months
Bestseller
IU, GermanyIU, GermanyMaster in International Management (120 ECTS)
  • 24 Months
Popular
IU, GermanyIU, GermanyB.Sc. Computer Science (180 ECTS)
  • 36 Months
Clark UniversityClark UniversityMaster of Business Administration
  • 23 Months
New
Golden Gate UniversityGolden Gate UniversityMaster of Business Administration
  • 20 Months
Clark University, USClark University, USMS in Project Management
  • 20 Months
New
Edgewood CollegeEdgewood CollegeMaster of Business Administration
  • 23 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
The American Business SchoolThe American Business SchoolMBA with specialization
  • 23 Months
New
Aivancity ParisAivancity ParisMSc Artificial Intelligence Engineering
  • 24 Months
Aivancity ParisAivancity ParisMSc Data Engineering
  • 24 Months
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGrad KnowledgeHutupGrad KnowledgeHutData Engineer Bootcamp
  • Self-Paced
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
KnowledgeHut upGradKnowledgeHut upGradBackend Development Bootcamp
  • Self-Paced
upGradupGradUI/UX Bootcamp
  • 3 Months
upGradupGradCloud Computing Bootcamp
  • 7.5 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 5 Months
upGrad KnowledgeHutupGrad KnowledgeHutSAFe® 6.0 POPM Certification
  • 16 Hours
upGradupGradDigital Marketing Accelerator Program
  • 05 Months
upGradupGradAdvanced Certificate Program in GenerativeAI
  • 4 Months
New
upGradupGradData Science Bootcamp with AI
  • 6 Months
Popular
upGradupGradFull Stack Software Development Bootcamp
  • 6 Months
Bestseller
upGradupGradUI/UX Bootcamp
  • 3 Months
PwCupGrad CampusCertification Program in Financial Modelling & Analysis in association with PwC India
  • 4 Months
upGradupGradCertificate Course in Business Analytics & Consulting in association with PwC India
  • 06 Months
upGradupGradDigital Marketing Accelerator Program
  • 05 Months

What is BFS Algorithm? Breath First Search Algorithm Explained

Updated on 12 October, 2023

4.05K+ views
9 min read

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.  

Read on to learn about BFS.

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

    add start_vertex to visited

    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

                add neighbour to visited

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.

Frequently Asked Questions (FAQs)

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.