--- title: "Searching: BFS vs DFS comparison" subject: "Artificial Intelligence" chapter: 3 key: "semester_6/artificial_intelligence:blind-search-dfs-bfs-compare" source: https://www.bctengineer.com/q/semester_6/artificial_intelligence/blind-search-dfs-bfs-compare site: BCT Engineering --- # Searching: BFS vs DFS comparison Artificial Intelligence · Chapter 3: Search Techniques - Asked in: 2069 Poush, 9 marks; 2072 Asoj, 9 marks; 2072 Magh, 2+7 marks; 2073 Bhadra, 4+5 marks; 2070 Magh, 7 marks (asked 5 times) - Video: [Time & Space Complexity of BFS and DFS | Artificial Intelligence](https://www.youtube.com/watch?v=_Ky9w2zF8JM) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/artificial_intelligence/blind-search-dfs-bfs-compare - Whole chapter: https://www.bctengineer.com/md/semester_6/artificial_intelligence/chapter-3 ## Question Why is searching necessary in AI? What is blind search? Explain Breadth First Search and Depth First Search with an example and compare their performance criteria (space and time complexity). ## Short answer Search is needed when no direct algorithm exists; blind search uses only problem definition. BFS expands shallowest nodes with FIFO queue, complete and optimal, O(b^d) time and space. DFS expands deepest with LIFO stack, incomplete, O(b^m) time and O(bm) space. ## Answer #### Why searching is necessary in AI For most AI problems (puzzles, route finding, planning, game playing) there is no direct algorithm that gives the solution. The problem is modelled as a **state space** and the solution is found by searching for a sequence of actions from the initial state to the goal. Search is also needed to find the *best* solution among many and to explore alternatives systematically. #### Blind (uninformed) search A **blind search** uses only the problem definition (initial state, operators, goal test). It has **no additional knowledge** about how close a state is to the goal, and expands nodes in a fixed order. Examples: BFS, DFS, uniform-cost, depth-limited and iterative deepening search. #### Example tree used for both searches ```text A / \ B C / \ / \ D E F G(goal) ``` #### Breadth First Search (BFS) Expands the shallowest unexpanded node first, using a **FIFO queue**. ```text 1. Put start node in queue. 2. Remove first node n; if goal -> stop. 3. Add all children of n to the END of the queue. 4. Repeat from step 2. ``` Order of visiting: **A, B, C, D, E, F, G**. Queue: [A] → [B,C] → [C,D,E] → [D,E,F,G] ... goal G found at depth 2. #### Depth First Search (DFS) Expands the deepest unexpanded node first, using a **LIFO stack** (or recursion). ```text 1. Put start node on stack. 2. Pop node n; if goal -> stop. 3. Push children of n on the TOP of the stack. 4. Repeat from step 2. ``` Order of visiting: **A, B, D, E, C, F, G**. It goes down a branch until it reaches a leaf or dead end, then backtracks. #### Comparison of performance criteria Let *b* = branching factor, *d* = depth of shallowest goal, *m* = maximum depth of the tree. | Criterion | BFS | DFS | |---|---|---| | Data structure | Queue (FIFO) | Stack (LIFO) | | Completeness | Yes (if b finite) | No (can loop in infinite/cyclic space); yes in finite tree | | Optimality | Yes, if all step costs are equal | No | | Time complexity | O(b^d) | O(b^m) | | Space complexity | O(b^d), all nodes kept in memory | O(b·m), only one path with siblings | | Finds | Shallowest goal | First goal found on the leftmost deep path | | Best suited for | Shortest path, goal near root | Deep solutions, limited memory | **Remarks:** BFS is complete and optimal but needs exponential memory (the main drawback). DFS needs far less memory but may get stuck in infinite paths and may find a longer solution. For example with b = 10 and d = 6, BFS may store about 10^6 nodes while DFS stores about 60. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What defines a blind (uninformed) search? A. It uses a heuristic to estimate distance to the goal B. It uses only the problem definition and has no knowledge of how close a state is to the goal C. It always finds the optimal path D. It never uses a queue or stack Answer: B. Blind search has only the initial state, operators and goal test, so it expands nodes in a fixed order without goal-directed knowledge. (Key point: Blind search) 2. For the tree A-(B,C), B-(D,E), C-(F,G), which pair is correct? A. BFS uses a stack and visits A, B, D, E, C, F, G B. BFS uses a FIFO queue and visits A, B, C, D, E, F, G C. DFS uses a FIFO queue and visits A, B, C, D, E, F, G D. DFS uses a LIFO stack and visits A, B, C, D, E, F, G Answer: B. BFS expands level by level with a FIFO queue; DFS uses a LIFO stack and goes deep first (A, B, D, E, C, F, G). (Key point: BFS data structure and order) 3. Why is BFS space complexity O(b^d) while DFS is only O(b·m)? A. BFS keeps all nodes of the frontier in memory, DFS keeps only the current path with its siblings B. DFS stores the entire tree C. BFS never backtracks, so it stores nothing D. DFS uses a queue that holds one node Answer: A. BFS must hold every node at the current level, which grows exponentially; DFS stores only one path and the siblings along it. (Key point: Space complexity) 4. Which statement about BFS and DFS is correct? A. DFS is complete and optimal in cyclic spaces B. BFS is complete and optimal (equal step costs) but needs exponential memory; DFS may get stuck in infinite paths C. BFS is not complete but uses little memory D. Both have time complexity O(b^m) Answer: B. BFS finds the shallowest goal with equal costs but at a large memory cost. DFS needs little memory but can follow infinite paths and is not optimal. (Key point: Completeness and optimality) ## Related in Artificial Intelligence - [Informed vs blind search; DFS vs BFS](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Ainformed-vs-blind-search-dfs-bfs) — Artificial Intelligence, chapter 3 ## Related in other subjects - [Differences between DFS and BFS](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adfs-vs-bfs-differences) — Data Structure and Algorithm, chapter 10 - [BFS and DFS with example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abfs-dfs-explain-example) — Data Structure and Algorithm, chapter 10, asked 4× - [Complexity of binary search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-complexity) — Data Structure and Algorithm, chapter 8