Design & Analysis of Algorithms - Vol 1 | 20. Breadth First Search (BFS) by Abraham | Learn Smarter
K12 Students

Academics

AI-Powered learning for Grades 8–12, aligned with major Indian and international curricula.

Professionals

Professional Courses

Industry-relevant training in Business, Technology, and Design to help professionals and graduates upskill for real-world careers.

Games

Interactive Games

Fun, engaging games to boost memory, math fluency, typing speed, and English skills—perfect for learners of all ages.

Typing
Memory
Math
English Adventures
Knowledge
20. Breadth First Search (BFS)

This chapter discusses the Breadth First Search (BFS) algorithm for exploring graphs, emphasizing the methods for systematically finding paths between vertices. It explains the representation of graphs, the data structures used in BFS, and the way BFS operates, including complexities and how to track the shortest path between nodes. BFS is shown to efficiently explore graphs while providing distance information when needed.

Enroll to start learning

You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.

Sections

  • 20.1

    Breadth First Search (Bfs)

    Breadth First Search (BFS) is an algorithm used to explore graphs systematically by visiting all vertices at the present depth prior to moving on to vertices at the next depth level.

    Learning Practice

  • 20.2

    Graph Representation

    This section discusses the representation of graphs using data structures and explores the breadth-first search (BFS) algorithm for graph traversal.

    Learning Practice

  • 20.2.1

    Adjacency Matrix

    This section introduces the concept of an adjacency matrix, a way to represent graphs and discusses its applications in the breadth-first search algorithm.

    Learning Practice

  • 20.2.2

    Adjacency List

    This section explains how to represent graphs using adjacency lists and how this representation supports breadth-first search (BFS) algorithms.

    Learning Practice

  • 20.3

    Bfs Algorithm

    The Breadth First Search (BFS) algorithm systematically explores a graph level by level to find paths between vertices.

    Learning Practice

  • 20.3.1

    Exploration Strategy

    This section introduces the Breadth-First Search (BFS) algorithm, detailing how to systematically explore a graph and identify connections between vertices.

    Learning Practice

  • 20.3.2

    Data Structures For Bfs

    This section covers the data structures essential for implementing the Breadth First Search (BFS) algorithm, detailing graph representation techniques, tracking visited vertices, and queue usage.

    Learning Practice

  • 20.3.3

    Pseudo Code For Bfs

    This section introduces the algorithm for Breadth-First Search (BFS), detailing its pseudo code, data structures used, and its complexity analysis.

    Learning Practice

  • 20.3.4

    Example Of Bfs Execution

    This section discusses the concept of Breadth First Search (BFS) for exploring graphs, explaining how it operates, its implementation, and its efficiency.

    Learning Practice

  • 20.3.5

    Formal Code For Bfs

    This section provides an in-depth explanation of the Breadth First Search (BFS) algorithm, including its implementation details and efficiency.

    Learning Practice

  • 20.3.6

    Complexity Analysis Of Bfs

    This section covers the complexity analysis of the Breadth-First Search (BFS) algorithm, including its implementation and performance using different graph representations.

    Learning Practice

  • 20.3.7

    Input Size In Graphs

    This section discusses the representation of graphs, focusing on breadth-first search (BFS) for exploring connectivity between vertices.

    Learning Practice

  • 20.4

    Path Reconstruction In Bfs

    This section discusses the breadth-first search (BFS) algorithm, focusing on how paths can be reconstructed using parent pointers.

    Learning Practice

  • 20.4.1

    Tracking Parent Vertices

    The section explores the Breadth First Search (BFS) algorithm for exploring graphs, emphasizing the tracking of parent vertices to reconstruct paths.

    Learning Practice

  • 20.4.2

    Tracking Levels

    This section discusses the breadth-first search algorithm for graph traversal, focusing on how it tracks levels and connectivity between vertices.

    Learning Practice

  • 20.4.3

    Reconstructing Paths In Bfs

    This section discusses the Breadth-First Search (BFS) algorithm, focusing on how to explore paths within a graph and reconstruct them.

    Learning Practice

  • 20.5

    Shortest Path In Unweighted Graphs

    This section introduces the concept of finding the shortest path in unweighted graphs using Breadth First Search (BFS).

    Learning Practice

  • 20.5.1

    Shortest Path Properties

    This section discusses the properties of the shortest path in graphs using the Breadth First Search (BFS) algorithm.

    Learning Practice

References

ch20.pdf

Class Notes

Memorization

What we have learnt

  • Graphs can be represented u...
  • The BFS algorithm explores ...
  • BFS can be utilized to reco...

Final Test

Revision Tests