W10_L4: Breadth-first search

Welcome to Week 10 Lecture 4 of the course "Mathematics for Data Science I" by Profs. Neelesh Upadhye, Madhavan Mukund. Full Course: https://study.iitm.ac.in/ds/course_pages/BSMA1001.html Video Overview This lecture introduces the concept of reachability in graphs and how to systematically explore a graph to determine if a target vertex is reachable from a source vertex. We revisit two common graph representations — the adjacency matrix and the adjacency list — and then delve into Breadth-First Search (BFS), a method for exploring a graph level by level. The lecture explains how to implement BFS using a queue, and extends the method to track both the path and the shortest distance between vertices. About IIT Madras' online Bachelor of Science programme IIT Madras offers four-year BS programmes that aim to provide quality education to all, irrespective of age, educational background, or location. The BS programme has multiple levels, which provide flexibility to students to exit at any of these levels. Depending on the courses completed and credits earned, the learner can receive a Foundation Certificate from IITM CODE (Centre for Outreach and Digital Education), Diploma(s) from IIT Madras, or BSc/BS Degrees from IIT Madras. For more details, visit: https://www.iitm.ac.in/academics/study-at-iitm/non-campus-bs-programmes #graph #reachability #adjacencyMatrix #adjacencyList #breadthFirstSearch #BFS #graphTraversal #dataStructures #algorithms #shortestPath #queue #vertex #edge #graphRepresentation