> 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-depth-first-search-dfs.md). # Practical 1 (A)- Depth First Search (DFS) **Language used:** Python 3 (standard library only, uses plain lists and recursion) **Aim:** Implement Depth First Search to find a path between two cities on a road map. *** ### 2.1 What is DFS, in simple words Imagine walking through a maze by always picking the first corridor you see, and following it as far as it goes, before ever backing up to try a different corridor. That is DFS. * It picks a neighbour of the current city and goes there immediately. * From that new city, it again picks a neighbour and goes there immediately. * It keeps diving deeper and deeper down one single path. * Only if it hits a dead end (a city with no new neighbours left) does it backtrack and try a different branch. DFS naturally uses a **stack** (Last In, First Out) instead of a queue. In this code, the "stack" is simply the list of visited cities, combined with the call stack created by the function calling itself (recursion). ```mermaid flowchart TD A[Arad] --> Z[Zerind] Z --> O[Oradea] O --> S[Sibiu] S --> F[Fagaras] F --> B[Bucharest - GOAL] ``` DFS commits to one path, Arad to Zerind to Oradea to Sibiu to Fagaras to Bucharest, and only backtracks if it hits a dead end. *** ### 2.2 The map we are searching (Romania road map) Same Romania map used in Practical 1. ```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 ``` *** ### 2.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 = 'Bucharest' result = '' def DFS(city, visitedstack): global result found = 0 result = result + ' ' + city visitedstack.append(city) if city == goal: return 1 for eachcity in dict_gn[city].keys(): if eachcity not in visitedstack: found = DFS(eachcity, visitedstack) if found: return found def main(): visitedstack = [] DFS(start, visitedstack) print("IDFS Traversal from", start, "to", goal, "is:") print(result) main() ``` *** ### 2.4 Line by line explanation | Line | What it does | | --------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `import queue as Q` | Imported here too, but this DFS implementation does not actually use `Q`. It uses a plain Python list (`visitedstack`) as its stack instead. | | `dict_gn = { ... }` | Same Romania map graph as Practical 1. | | `start = 'Arad'` | Starting city. | | `goal = 'Bucharest'` | This time we search for a path from Arad to Bucharest. | | `result = ''` | An empty string that collects the path as text, same idea as Practical 1. | | `def DFS(city, visitedstack):` | Defines DFS. Takes the current `city`, and `visitedstack`, a list used as a stack that tracks the path taken so far. | | `global result` | Same reason as in BFS, use the outer `result` variable rather than creating a new local one. | | `found = 0` | A local flag: has the goal been found yet, in the branch currently being explored? Starts at 0, meaning not yet found. | | `result = result + ' ' + city` | As soon as we step into a city, even before checking its neighbours, we record it in the result. This is different from BFS, where cities were recorded at the moment of discovery, not at the moment of entry. | | `visitedstack.append(city)` | Push the current city onto the visited stack. This marks it as "on our current path," so we never revisit it and loop forever. | | `if city == goal: return 1` | Base case of the recursion. If we have arrived at the goal, stop immediately and signal success by returning 1. | | `for eachcity in dict_gn[city].keys():` | Loop over the neighbours of the current city, same idea as BFS, but what happens next is very different. | | `if eachcity not in visitedstack:` | Only go to a neighbour we have not already visited on this path. This prevents cycles. | | `found = DFS(eachcity, visitedstack)` | Recursive call, this is the "go deep" step. Instead of queueing up all neighbours like BFS does, DFS immediately dives into one neighbour, all the way down, before even looking at the next neighbour. This call only returns once that entire branch has been fully explored, either the goal was found, or it was a dead end. | | `if found: return found` | If that recursive branch found the goal, this propagates that success back up through every parent call. This is how the recursion "unwinds" and stops everywhere once the goal is found. | | `def main(): ...` | Sets up an empty stack, `visitedstack = []`, starts the search, and prints the path. | *** ### 2.5 Why this is called Depth First, and how it differs from BFS * BFS used an explicit `queue.Queue()` object, and recursed on `cityq.get()`, the oldest discovered city, giving a breadth first order. * DFS here uses a plain list as a stack (`visitedstack`), and recurses immediately into the first unvisited neighbour it finds, without waiting to look at siblings first, giving a depth first order. * The recursion itself behaves like the stack. Each call to `DFS()` waits for its recursive child call to finish, exactly like a stack of plates, last one placed is the first one removed. *** ### 2.6 Step by step trace (path taken) ```mermaid flowchart TD Arad -->|first neighbour tried| Zerind Zerind -->|Arad already visited, try Oradea| Oradea Oradea -->|Zerind already visited, try Sibiu| Sibiu Sibiu -->|Arad and Oradea visited, try Fagaras| Fagaras Fagaras -->|Sibiu visited, try Bucharest| Bucharest((Bucharest, GOAL)) ``` DFS never even looks at Timisoara, Lugoj, Rimnicu Vilcea, or most of the map, because it found the goal while going deep down the first available branch at every step, and stopped immediately once `found` became true. *** ### 2.7 Output ``` IDFS Traversal from Arad to Bucharest is: Arad Zerind Oradea Sibiu Fagaras Bucharest ``` Only 6 cities are printed, much shorter than BFS's output, because DFS commits to a path and stops the instant it hits the goal, without exploring every alternative branch along the way. *** ### 2.8 Quick recap for viva * DFS explores as deep as possible down one path, using a stack (or recursion), before backtracking. * It does not guarantee the shortest path. It got lucky in this example, a different neighbour order in the dictionary could have taken much longer to reach Bucharest. * It is generally more memory efficient than BFS, since it only needs to remember the current path, not the whole frontier. * Like BFS, this is also uninformed search, no heuristic or estimated distance to the goal is used, only the connections between cities. --- # 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-depth-first-search-dfs.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.