> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/ai-college-notes/practical-1-a-breadth-first-search-bfs.md). # Practical 1 (A) - Breadth First Search (BFS) **Language used:** Python 3 (standard library only, uses the built-in `queue` module) **Aim:** Implement Breadth First Search to find a path between two cities on a road map. *** ### 1.1 What is BFS, in simple words Imagine dropping a stone in still water. The ripples spread out evenly in all directions, one ring at a time. That is exactly how BFS explores a graph: * First it looks at the starting point. * Then it looks at ALL of the starting point's direct neighbours. * Then it looks at ALL of those neighbours' neighbours. * It keeps going ring by ring (level by level) until it finds the goal. Because it always finishes one full level before moving to the next, BFS guarantees it finds the path with the **fewest number of steps** (hops) to the goal. BFS uses a **queue** to do this. A queue works like a line at a ticket counter: first person in line, first person served (First In, First Out, or FIFO). ```mermaid flowchart TD A[Arad - Level 0] --> Z[Zerind - Level 1] A --> S[Sibiu - Level 1] A --> T[Timisoara - Level 1] Z --> O[Oradea - Level 2] S --> F[Fagaras - Level 2] S --> R[Rimnicu Vilcea - Level 2] T --> L[Lugoj - Level 2] ``` BFS finishes visiting everything at Level 1 before it ever touches Level 2. *** ### 1.2 The map we are searching (Romania road map) This is the well known example map from the AI textbook *Artificial Intelligence: A Modern Approach*, used to teach search algorithms. ```mermaid graph LR Arad --75--- Zerind Arad --140--- Sibiu Arad --118--- Timisoara Zerind --71--- Oradea Oradea --151--- Sibiu Sibiu --99--- Fagaras Sibiu --80--- RimnicuVilcea Fagaras --211--- Bucharest RimnicuVilcea --146--- Craiova RimnicuVilcea --97--- Pitesti Pitesti --101--- Bucharest Craiova --120--- Drobeta Drobeta --75--- Mehadia Mehadia --70--- Lugoj Lugoj --111--- Timisoara Bucharest --90--- Giurgiu Bucharest --85--- Urziceni Urziceni --98--- Hirsova Hirsova --86--- Eforie Urziceni --142--- Vaslui Vaslui --92--- Iasi Iasi --87--- Neamt ``` *** ### 1.3 The full code ```python import queue as Q dict_gn = { 'Arad': {'Zerind': 75, 'Sibiu': 140, 'Timisoara': 118}, 'Zerind': {'Arad': 75, 'Oradea': 71}, 'Oradea': {'Zerind': 71, 'Sibiu': 151}, 'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'Rimnicu Vilcea': 80}, 'Timisoara': {'Arad': 118, 'Lugoj': 111}, 'Lugoj': {'Timisoara': 111, 'Mehadia': 70}, 'Mehadia': {'Lugoj': 70, 'Drobeta': 75}, 'Drobeta': {'Mehadia': 75, 'Craiova': 120}, 'Craiova': {'Drobeta': 120, 'Rimnicu Vilcea': 146, 'Pitesti': 138}, 'Rimnicu Vilcea': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97}, 'Fagaras': {'Sibiu': 99, 'Bucharest': 211}, 'Pitesti': {'Rimnicu Vilcea': 97, 'Craiova': 138, 'Bucharest': 101}, 'Bucharest': {'Fagaras': 211, 'Pitesti': 101, 'Giurgiu': 90, 'Urziceni': 85}, 'Giurgiu': {'Bucharest': 90}, 'Urziceni': {'Bucharest': 85, 'Hirsova': 98, 'Vaslui': 142}, 'Hirsova': {'Urziceni': 98, 'Eforie': 86}, 'Eforie': {'Hirsova': 86}, 'Vaslui': {'Urziceni': 142, 'Iasi': 92}, 'Iasi': {'Vaslui': 92, 'Neamt': 87}, 'Neamt': {'Iasi': 87} } start = 'Arad' goal = 'Neamt' result = '' def BFS(city, cityq, visitedq): global result if city == start: result = result + ' ' + city for eachcity in dict_gn[city].keys(): if eachcity == goal: result = result + ' ' + eachcity return if eachcity not in cityq.queue and eachcity not in visitedq.queue: cityq.put(eachcity) result = result + ' ' + eachcity visitedq.put(city) BFS(cityq.get(), cityq, visitedq) def main(): cityq = Q.Queue() visitedq = Q.Queue() BFS(start, cityq, visitedq) print("BFS Traversal from", start, "to", goal, "is:") print(result) main() ``` *** ### 1.4 Line by line explanation | Line | What it does | | -------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | `import queue as Q` | Brings in Python's built in queue module, renamed to `Q` for short. Gives us `Q.Queue()`, a ready made FIFO queue. | | `dict_gn = { ... }` | Our graph, stored as a dictionary of dictionaries. Outer key equals a city. Inner dictionary equals `{neighbour: distance}`. This is the Romania map shown above, written in Python. | | `start = 'Arad'` | The city we begin searching from. | | `goal = 'Neamt'` | The city we are trying to reach. | | `result = ''` | An empty string that will collect the traversal order as we go. This is what gets printed at the end. | | `def BFS(city, cityq, visitedq):` | Defines the BFS function. It takes the current city being processed, the frontier queue (`cityq`, cities discovered but not yet processed), and the visited queue (`visitedq`, cities already processed). | | `global result` | Tells Python to use the `result` variable defined outside this function, instead of creating a new local one. | | `if city == start: result = result + ' ' + city` | The very first time BFS runs, `city` is `'Arad'` (the start), so we manually add it to the result. This is needed because normally cities get added to `result` only when they are discovered as a neighbour, not when they are processed, and the start city is never anyone's neighbour. | | `for eachcity in dict_gn[city].keys():` | Loop over every neighbour of the current city. For `'Arad'`, this loops over `'Zerind'`, `'Sibiu'`, `'Timisoara'`. | | `if eachcity == goal: ... return` | Goal check. If a neighbour we just found is the goal city, add it to the result and immediately stop the whole function. The goal has been found, so there is no need to search further. | | `if eachcity not in cityq.queue and eachcity not in visitedq.queue:` | Only consider a neighbour if it has not already been queued to be visited, or already visited. This avoids repeats and infinite loops. | | `cityq.put(eachcity)` | Add this newly discovered neighbour to the back of the frontier queue. It will be processed only after everything already in the queue, keeping the FIFO order. | | `result = result + ' ' + eachcity` | Record that we discovered this city, by appending it to our output string. | | `visitedq.put(city)` | Once we are done looking at all of the current city's neighbours, mark the current city as fully visited. | | `BFS(cityq.get(), cityq, visitedq)` | Recursive call. `cityq.get()` removes and returns the city at the front of the queue (the oldest discovered city) and BFS is called again on it. This is what makes the search continue level by level. | | `def main():` | Sets up two empty queues and starts the search. | | `cityq = Q.Queue()` and `visitedq = Q.Queue()` | Fresh empty frontier and visited queues. | | `BFS(start, cityq, visitedq)` | Starts the search from `'Arad'`. | | `print(...)` | Displays the final traversal path stored in `result`. | | `main()` | Actually runs the program. Without this line, nothing would execute. | *** ### 1.5 Step by step trace (how the frontier queue changes) ```mermaid flowchart TD Start([Start: city = Arad]) --> Check{Is city the start city?} Check -->|yes| AddStart[Add Arad to result] Check -->|no| Loop AddStart --> Loop[Look at each neighbour of city] Loop --> GoalCheck{Is this neighbour the goal?} GoalCheck -->|yes| Found[Add to result, stop searching] GoalCheck -->|no| Seen{Already queued or visited?} Seen -->|yes| Loop Seen -->|no| Enqueue[Put neighbour in cityq, add to result] Enqueue --> Loop Loop -->|done with all neighbours| MarkVisited[Put city in visitedq] MarkVisited --> Next[Recursive call: BFS on next city from cityq] Next --> Check ``` | Step | City being processed | Frontier queue after this step | Visited so far | | ---- | -------------------- | ------------------------------------------ | ------------------- | | 1 | Arad | Zerind, Sibiu, Timisoara | (none) | | 2 | Zerind | Sibiu, Timisoara, Oradea | Arad | | 3 | Sibiu | Timisoara, Oradea, Fagaras, Rimnicu Vilcea | Arad, Zerind | | 4 | Timisoara | Oradea, Fagaras, Rimnicu Vilcea, Lugoj | Arad, Zerind, Sibiu | Notice how BFS always finishes discovering everything at the current level before it moves deeper, exactly like the ripple in water idea from section 1.1. *** ### 1.6 Output ``` BFS Traversal from Arad to Neamt is: Arad Zerind Sibiu Timisoara Oradea Fagaras Rimnicu Vilcea Lugoj Bucharest Craiova Pitesti Mehadia Giurgiu Urziceni Drobeta Hirsova Vaslui Eforie Iasi Neamt ``` Each city appears in the order it was discovered (added to `cityq`), not necessarily the order it was fully processed. Bucharest shows up fairly early, as a neighbour of Fagaras, even though many other cities are processed around the same time. *** ### 1.7 Quick recap for viva * BFS explores level by level using a queue, so cities closer to the start are always found before cities further away. * It guarantees the shortest path in terms of number of hops. * The recursive call `BFS(cityq.get(), cityq, visitedq)` is what keeps the search moving forward through the queue. * This is called uninformed search, because the algorithm has no extra knowledge like straight line distance to the goal. It only knows which cities are connected to which. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://alham-rizvi.gitbook.io/alhamrizvi/ai-college-notes/practical-1-a-breadth-first-search-bfs.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.