---

📘 Depth-First Search (DFS)

1️⃣ Introduction

Depth-First Search (DFS) is a fundamental graph traversal algorithm.

🔹 Definition

DFS explores a graph by going as deep as possible along each branch before backtracking.

It uses a stack (LIFO) — either explicitly or via recursion.

---

2️⃣ Key Idea of DFS

• Start from a source vertex
• Explore one neighbor completely before moving to others
• If no unvisited neighbor → backtrack

---

3️⃣ Working Principle

🔹 Steps

1. Start from a source vertex
2. Mark it as visited
3. Visit one unvisited adjacent vertex
4. Repeat recursively
5. If no unvisited neighbor → backtrack

---

4️⃣ Algorithm (DFS)

🔹 Recursive Pseudocode

DFS(G, u):
   mark u as visited
   print u

   for each vertex v adjacent to u:
       if v is not visited:
           DFS(G, v)

---

🔹 Iterative Version (Using Stack)

DFS(G, s):
   create stack S
   push s into S

   while S is not empty:
       u = pop(S)

       if u is not visited:
           mark u as visited
           print u

           for each neighbor v of u:
               push v into stack

---

5️⃣ Example

🔹 Graph:

      A
     / \
    B   C
   / \   \
  D   E   F

---

🔹 DFS Traversal (Starting from A)

A → B → D → E → C → F

✔ Goes deep first, then backtracks

---

6️⃣ Recursion Trace (Concept)

• Visit A
• Go to B
• Go to D → no more neighbors → backtrack
• Go to E → backtrack
• Go to C
• Go to F

---

7️⃣ Time Complexity

🔹 Using Adjacency List

[
O(V + E)
]

🔹 Using Adjacency Matrix

[
O(V^2)
]

---

8️⃣ Space Complexity

• Recursive stack / explicit stack → O(V)
• Visited array → O(V)

---

9️⃣ Characteristics of DFS

✔ Depth-wise traversal
✔ Uses recursion or stack
✔ Backtracking-based
✔ Does not guarantee shortest path

---

🔟 Applications of DFS

• Cycle detection in graphs
• Topological sorting
• Connected components
• Maze solving
• Path finding
• Strongly connected components

---

1️⃣1️⃣ Advantages

✔ Simple to implement
✔ Uses less memory than BFS
✔ Useful for deep traversal problems

---

1️⃣2️⃣ Disadvantages

✖ Does not guarantee shortest path
✖ May go deep into unnecessary paths
✖ Recursive stack overflow (for large graphs)

---

1️⃣3️⃣ DFS vs BFS

Feature	DFS	BFS
Data Structure	Stack	Queue
Traversal	Depth-first	Level-first
Shortest Path	No	Yes
Memory	Less	More

---

🔚 Conclusion

Depth-First Search is a powerful graph traversal algorithm that explores nodes deeply before backtracking.

DFS is ideal for problems requiring full exploration like cycle detection and topological sorting.

---

📌 Exam Tip

👉 Always include:

• Recursive algorithm
• Stack concept
• Example traversal
• Complexity

---