Artificial Intelligence : Unit - 2 Part - 4 : Depth First Search (DFS)

                                                                     UNIT - II

Topic: Depth First Search (DFS)

---

Introduction

What is Depth First Search?

Depth First Search (DFS) is an uninformed search strategy that explores as far as possible along each branch before backtracking.
It dives deep into the search tree before exploring siblings (goes depth by depth instead of breadth).

---

Characteristics of DFS

Feature	Description
Type	Uninformed Search
Search Direction	Depth-first (vertical expansion)
Data Structure	Stack (LIFO - Last In, First Out)
Completeness	❌ No (Fails for infinite/deep spaces without cutoff)
Optimality	❌ No (Doesn’t always find the shortest path)
Time Complexity	O(b^d), where b = branching factor, d = max depth
Space Complexity	O(b*d) → stores a single path from root to leaf

Part C: How DFS Works – Step by Step

1.     Start from the initial node and push it onto a stack.

2.     Repeat the following steps until the stack is empty:

o   Pop the top node from the stack.

o   If it is the goal node, return the solution.

o   Else, expand the node (generate its children).

o   Push the child nodes onto the top of the stack.

3.     If the stack becomes empty without finding the goal, return failure.

Key Principles of DFS:

·        Deepest node first: Explores one path fully before backtracking.

·        Stack-based implementation: Uses Last-In-First-Out (LIFO) behavior.

·        Backtracking: Automatically happens when no further expansion is possible.

·        Not optimal: Might return a longer path or even miss the goal in infinite trees.

---

Part D: DFS Algorithm (Pseudo-code)

DFS(initial_node, goal_test):

   create a stack S

   add initial_node to S

   create a visited list

   while S is not empty:

       current_node = S.pop()

       if current_node satisfies goal_test:

           return success (path found)

           mark current_node as visited

       for each neighbor of current_node:

           if neighbor not visited:

               push neighbor to S

---

The DFS Algorithm Process

1. Initialization:

·        Start with the initial node.

·        Create an empty stack and push the root node.

·        Create a visited set.

2. Main Loop:

·        Pop a node from the stack.

·        If it's the goal, return the solution.

·        Otherwise, expand and push all unvisited children to the stack.

·        Mark current node as visited.

3. Termination:

·        If the stack becomes empty without finding the goal, return failure.

---

Example: Solving a Simple Pathfinding Problem

Graph: Cities connected in a tree
Goal: Find path from A to F using DFS

Step-by-Step Execution:

1.     Initialization:

o   Stack: [A]

o   Visited: {}

2.     Depth 0:

o   Pop A → A ≠ F

o   Expand A → [C, B] (assuming right-to-left expansion)

o   Stack: [C, B]

o   Visited: {A}

3.     Depth 1:

o   Pop B → B ≠ F

o   Expand B → [E, D]

o   Stack: [C, E, D]

o   Visited: {A, B}

4.     Depth 2:

o   Pop D → D ≠ F

o   No children

o   Stack: [C, E]

o   Visited: {A, B, D}

o   Pop E → E ≠ F

o   No children

o   Stack: [C]

o   Visited: {A, B, D, E}

5.     Backtrack & explore next path:

o   Pop C → C ≠ F

o   Expand C → [F]

o   Stack: [F]

o   Visited: {A, B, D, E, C}

6.     Goal Found:

o   Pop F → F = Goal

o   Return path: A → C → F

---

Real-Life Examples of DFS

Scenario	Explanation
Puzzle Solving	DFS explores all possibilities (e.g., Sudoku, maze)
Program Execution	Function calls follow DFS (stack-based)
File System Search	Traverses directory trees to search or list contents
Game Tree Search	DFS used in algorithms like Minimax with pruning

Properties of DFS

1.     Completeness: ❌ Not complete in infinite trees (may go infinitely deep)

2.     Optimality: ❌ Not guaranteed to find shortest path

3.     Time Complexity: O(b^d), b = branching factor, d = max depth

4.     Space Complexity: O(b*d) (less memory than BFS)

5.     Memory Usage: Efficient – stores only the path being explored

---

Advantages and Disadvantages

✅ Advantages:

·        Low memory usage (O(b*d))

·        Simple and easy to implement

·        Useful when solutions are deep in the tree

·        Better for space-constrained problems

❌ Disadvantages:

·        Not complete (may loop forever in infinite spaces)

·        Not optimal (may return longer path)

·        May miss shallow solutions

---

Conclusion

Depth First Search is an essential AI search algorithm that efficiently explores deep paths. Though it’s not always optimal or complete, DFS is memory-efficient and useful in many real-world applications involving recursion, backtracking, or deep-tree structures.