🔷 2.Depth-First Search (DFS)

Questions:

Apply the Depth-First Search (DFS) algorithm to traverse the following tree and list the order of node visits.
Implement DFS for the following graph using a stack-based approach. Trace the steps to reach the goal node
Given a file system hierarchy, apply DFS to list all files and folders starting from the root directory. Show the traversal order. (Check at last)

🔷 2.Depth-First Search (DFS)

1.Definition:
DFS is an uninformed search strategy where:

The deepest node in the frontier is expanded first.
Search proceeds along one path as deep as possible, then backtracks to explore other paths.

✅ Key property:

It follows a path from root to a leaf node fully before considering sibling nodes.

🔷 2. When to use DFS?

The problem has a very large state space, but solutions are deep and memory is limited.

Example:

AI planning in logic programming (Prolog recursion).
Constraint satisfaction problems (backtracking in Sudoku solving).

2. How does DFS work?

✅ Implementation insights:

Often implemented as a tree search, without keeping a reached table (i.e., no memory of visited states).
Uses a stack (LIFO) data structure to manage the frontier.
Each expansion adds new deeper nodes to the top of the stack, which are expanded next.

🔷 3. Example: City Route Tree

City route tree:

A

/ \

B C

/ \ / \

D E F G

✔ Start from A (root).

✔ Order of exploration in DFS (Left-to-Right example):

A → B → D → E → C → F → G

Step by Step Expansion:

Start with root node A.

Stack: [A]

Expand A. Push its children B, C onto stack.

Stack: [C, B]

Pop B. Expand B. Push its children D, E onto stack.

Stack: [C, E, D]

Pop D. Expand D. (No children)

Stack: [C, E]

Pop E. Expand E. (No children)

Stack: [C]

Pop C. Expand C. Push its children F, G onto stack.

Stack: [G, F]

Pop F. Expand F. (No children)

Stack: [G]

Pop G. Expand G. (No children)

Stack: []

✔ Final Order of Expansion:
A → B → D → E → C → F → G

🔷 4. Implementation Insights

✔ Uses a LIFO (Last-In-First-Out) stack to store the frontier.

Frontier Stack (LIFO):

[Top] G → F → C → E → D → B → A [Bottom]

Stepwise Explanation of Stack Usage:

New nodes are pushed on top.
Expansion always happens from the top of the stack (deepest node).

🔷 Early Goal Test in DFS

✅ Checks if a node is the goal immediately upon popping from the stack.

Example:

Goal: E

Start with node A.

Push its children B, C onto stack (Right child pushed first for Left-to-Right expansion).
Stack: [C, B]

Pop B.

Is B the goal? ❌
Expand B. Push its children D, E onto stack (Right child E pushed first).
Stack: [C, E, D]

Pop D.

Is D the goal? ❌
D has no children, continue.
Stack: [C, E]

Pop E.

Is E the goal? ✅ ✔ Goal found immediately upon popping.

✅ Explanation:

Early Goal Test in DFS: Checks goal condition when a node is popped for expansion.
Finds first encountered solution, not necessarily the optimal or shortest path.

🔷 5. Key Properties of Depth-First Search (DFS)

Property	Explanation
✅ Completeness	❌ Not complete in infinite state spaces. Can get stuck exploring infinite paths without reaching the goal.
✅ Optimality	❌ Not optimal. Returns the first solution found, which may not be shortest or cheapest.
✅ Time Complexity	O(b^m) where b = branching factor, m = maximum depth. Exponential growth with depth.
✅ Space Complexity	O(bm). Very low memory usage compared to BFS because it only stores current path and unexpanded siblings.

🔷 DFS Completeness

Scenario:

A simple state tree representing cities connected linearly with an infinite branch.

...

Goal (G)

✅ Explanation:

Start at A
DFS goes deep down the infinite path, exploring A → B → C → D → … endlessly if goal is elsewhere.

Case 1: Completeness Issue

Goal is at a different branch not explored

/ \

B Goal(G)

...

✔ DFS Exploration Order:

A → B → C → D → … (goes infinitely deep along B branch)
❌ Never explores Goal(G) on other branch → Not complete in infinite state spaces.

🔷 DFS Optimality :

Case : Multiple paths to goal with different costs

/ \

B C

| |

Goal(G) Goal(G)

(cost=10) (cost=2)

✔ DFS Exploration Order:

A → B → Goal(G)
✔ Finds first goal at cost=10.
❌ Does not find optimal path via C with cost=2.
Not optimal. Returns first solution found, not necessarily cheapest.

🔷 DFS Time Complexity Formula: O(b^m)

✔️ Branching factor (b):
Each node has at most 2 children, so b = 2.

✔️ Maximum depth (m):
For example, m = 3.

✅ Calculation:

At depth 0: b⁰ = 1 node (A)
At depth 1: b¹ = 2 nodes (B, C)
At depth 2: b² = 4 nodes (D, E, F, G)

✔ Total nodes generated:
1 + 2 + 4 = 7 nodes

⚠ Memory usage:
Unlike BFS, DFS only stores up to bm nodes (path length and siblings), so it uses very little memory.

🔷 6. Backtracking Search

✅ What is Backtracking?

A variant of Depth-First Search (DFS) with even lower memory usage.
Key features:

Generates only one successor at a time (not all successors simultaneously).
Uses in-place modification of the current state instead of allocating new memory for each child state.
Requires the ability to undo actions when backtracking.

Strategy

Memory Component

Memory Formula

Explanation

DFS

Unvisited Siblings

O(bm)

Stores other children waiting to be explored at each level

Stores all path nodes + siblings.

Backtracking

Current path

O(m)

Stores nodes from root to current node.

✅ Combined: O(bm) memory usage in standard DFS.

Step by Step with Backtracking

Start at root node A.

Current Path: [A]

Expand A → choose B.

Current Path: [A, B]

Expand B → choose D.

Current Path: [A, B, D]

D has no children (goal not found).

Backtrack: Remove D, go back to B.
Current Path: [A, B]

Try next child of B → E.

Current Path: [A, B, E]

E has no children (goal not found).

Backtrack: Remove E, go back to B.
Current Path: [A, B]

All children of B explored.

Backtrack: Remove B, go back to A.
Current Path: [A]

Try next child of A → C.

Current Path: [A, C]

Expand C → choose F.

Current Path: [A, C, F]

F has no children (goal not found).

Backtrack: Remove F, go back to C.
Current Path: [A, C]

Try next child of C → G.

Current Path: [A, C, G]

G has no children (goal not found).

Backtrack: Remove G, go back to C.
Current Path: [A, C]

All children of C explored.

Backtrack: Remove C, go back to A.
Current Path: [A]

All nodes explored.

Example:

Strategy	Memory Calculation
Backtracking	O(m) = O(3) = 3 nodes stored maximum (path from A to leaf).
DFS	O(bm) = O(2×3) = 6 nodes (stores path + siblings).
BFS	O(b^d) = O(2^3) = 8 nodes (stores all nodes at each level).

📁 Example File System Structure (Tree Format)

Root
├── Folder1
│   ├── File1.txt
│   └── File2.txt
├── Folder2
│   └── SubFolder1
│       └── File3.txt
└── File4.txt

🔍 Applying DFS (Depth-First Search)

We use a stack-based or recursive approach to traverse the structure depth-first.

DFS Traversal Order (Pre-order traversal):

Root
Folder1
File1.txt
File2.txt
Folder2
SubFolder1
File3.txt
File4.txt

🧠 Explanation:

Start at the Root.
Go deep into Folder1 first → then visit its files.
Backtrack to Folder2, go into SubFolder1 → then its file.
Finally, visit File4.txt directly under Root.

✅ DFS Enhances Search Efficiency in File Systems:

Efficient for deep structures (e.g., nested folders).
Uses less memory than BFS (no full level storage).
Can be used for tasks like file searching, dependency resolution, or cyclic checks

🔷 2.Depth-First Search (DFS)

Questions:

Given a file system hierarchy, apply DFS to list all files and folders starting from the root directory. Show the traversal order. (Check at last)

🔷 2.Depth-First Search (DFS)

1.Definition: DFS is an uninformed search strategy where:

The deepest node in the frontier is expanded first.

Search proceeds along one path as deep as possible, then backtracks to explore other paths.

✅ Key property:

It follows a path from root to a leaf node fully before considering sibling nodes.

🔷 2. When to use DFS?

The problem has a very large state space, but solutions are deep and memory is limited.

Example:

AI planning in logic programming (Prolog recursion).

Constraint satisfaction problems (backtracking in Sudoku solving).

2. How does DFS work?

✅ Implementation insights:

Often implemented as a tree search, without keeping a reached table (i.e., no memory of visited states).

Uses a stack (LIFO) data structure to manage the frontier.

Each expansion adds new deeper nodes to the top of the stack, which are expanded next.

🔷 3. Example: City Route Tree

City route tree:

A

/ \

B C

/ \ / \

D E F G

✔ Start from A (root).

✔ Order of exploration in DFS (Left-to-Right example):

A → B → D → E → C → F → G

Step by Step Expansion:

Start with root node A.

Stack: [A]

Expand A. Push its children B, C onto stack.

Stack: [C, B]

Pop B. Expand B. Push its children D, E onto stack.

Stack: [C, E, D]

Pop D. Expand D. (No children)

Stack: [C, E]

Pop E. Expand E. (No children)

Stack: [C]

Pop C. Expand C. Push its children F, G onto stack.

Stack: [G, F]

Pop F. Expand F. (No children)

Stack: [G]

Pop G. Expand G. (No children)

Stack: []

✔ Final Order of Expansion: A → B → D → E → C → F → G

🔷 4. Implementation Insights

✔ Uses a LIFO (Last-In-First-Out) stack to store the frontier.

Frontier Stack (LIFO):

[Top] G → F → C → E → D → B → A [Bottom]

Stepwise Explanation of Stack Usage:

New nodes are pushed on top.

Expansion always happens from the top of the stack (deepest node).

🔷 Early Goal Test in DFS

✅ Checks if a node is the goal immediately upon popping from the stack.

Example:

Goal: E

Start with node A.

Push its children B, C onto stack (Right child pushed first for Left-to-Right expansion).

Stack: [C, B]

Pop B.

Is B the goal? ❌

Expand B. Push its children D, E onto stack (Right child E pushed first).

Stack: [C, E, D]

Pop D.

Is D the goal? ❌

D has no children, continue.

Stack: [C, E]

Pop E.

Is E the goal? ✅ ✔ Goal found immediately upon popping.

✅ Explanation:

Early Goal Test in DFS: Checks goal condition when a node is popped for expansion.

Finds first encountered solution, not necessarily the optimal or shortest path.

🔷 5. Key Properties of Depth-First Search (DFS)

Property

Explanation

✅ Completeness

❌ Not complete in infinite state spaces. Can get stuck exploring infinite paths without reaching the goal.

✅ Optimality

1.Definition:
DFS is an uninformed search strategy where:

✔ Final Order of Expansion:
A → B → D → E → C → F → G

✔️ Branching factor (b):
Each node has at most 2 children, so b = 2.

✔️ Maximum depth (m):
For example, m = 3.

At depth 0: b⁰ = 1 node (A)
At depth 1: b¹ = 2 nodes (B, C)
At depth 2: b² = 4 nodes (D, E, F, G)

✔ Total nodes generated:
1 + 2 + 4 = 7 nodes

⚠ Memory usage:
Unlike BFS, DFS only stores up to bm nodes (path length and siblings), so it uses very little memory.