BFS and DFS

🏰 Introduction: The Castle Maze

Imagine you are exploring a giant, dark castle looking for a hidden treasure chest. The castle has many rooms, and each room has doors leading to other rooms.

You have two different strategies to search the castle:

Strategy 1: The Fearless Diver (DFS - Depth First Search) You choose one door and run through it. You keep picking a new door in every room and running as deep into the castle as you possibly can until you hit a dead end. When you hit a wall, you back up one room and try a different door. You are diving deep!

Strategy 2: The Careful Mapper (BFS - Breadth First Search) You start in the entrance. First, you peek into all the rooms immediately connected to the entrance (Level 1). Only after you have checked all those nearby rooms do you step forward and check all the rooms connected to them (Level 2). You explore outwards like a ripple in a pond!

---

🤔 What are BFS and DFS?

DFS (Depth First Search) and BFS (Breadth First Search) are the two most famous algorithms for exploring Trees and Graphs (networks of connected data).

• DFS uses a Stack (or Recursion). It goes deep first. It is great for finding any path to a goal, or exploring every single possibility (like solving a maze or Sudoku).
• BFS uses a Queue. It goes wide first. It is the absolute best way to find the Shortest Path between two points, because it checks everything 1 step away, then 2 steps away, and so on.

---

✨ The Core Strategies

The DFS Formula (Recursion is your friend!)

1. Visit the current room.
2. Mark it as "Visited" (so you don't walk in circles).
3. Look at all connected doors.
4. For each door, recursively cast the DFS spell to dive into it!

The BFS Formula (Use a Line/Queue!)

1. Put your starting room into a Queue (a line).
2. While the line is not empty:
   • Take the first room out of the line.
   • Mark it "Visited".
   • Put all of its unvisited neighbors at the back of the line.

---

🎟️ Real-World Example: Finding a Friend's Phone Number

Imagine you need to find the phone number of someone named "Dave", and you can only ask your friends.

• DFS Way: You ask your best friend Alice. Alice doesn't know, so she asks her best friend Bob. Bob asks Charlie. You follow one single chain of friends as far as it goes until someone knows Dave.
• BFS Way: You send a text message to ALL of your immediate friends first. If none of them know Dave, you ask them to text ALL of their friends. You are searching in expanding circles!

---

🧩 Problem Walkthrough: Number of Islands

Imagine a grid (a map) of 1s (land) and 0s (water). We want to count how many separate islands there are.

The Strategy (Using DFS)

We will scan the map. Whenever we find a piece of land (1), we found a new island! We add 1 to our count. BUT, we then use DFS to explore that entire island and sink it (turn the 1s into 0s). We do this so we don't accidentally count the same island twice!

---

🚫 Common Mistakes

1. Forgetting to mark as Visited: If you don't change the 1 to a 0 (or keep a visited set), your DFS will bounce back and forth between two pieces of land forever!
2. Using DFS for Shortest Path: DFS will find a path, but rarely the shortest path. If a problem asks for the "shortest", "closest", or "minimum steps", you almost always want to use BFS.

---

🎮 Practice Problems

• Number of Islands — Practice grid DFS.
• Max Area of Island — A small twist on counting islands.
• Rotting Oranges — A perfect example of why BFS is used for spreading over time.