Depth-First Search (DFS)

Understanding recursive graph traversal and maze/path exploration (used in the a-maze-ing project).

---

Table of Contents

1. What is DFS?
2. Graph Traversal
3. DFS Mentality
4. Stack Behavior
5. Recursive Exploration
6. Visual Example
7. DFS Logic
8. Visited Nodes
9. Recursive Backtracking
10. Iterative DFS
11. Complexity
12. DFS vs BFS
13. DFS in Maze Generation
14. Fly-in Connection
15. Mental Model

---

1️⃣ What is DFS?

DFS means:

Depth-First Search

It is an algorithm used to:

• traverse graphs
• explore paths deeply
• generate mazes
• search recursive structures

---

DFS explores:

go as deep as possible first

ONLY after:

backtrack

---

2️⃣ Graph Traversal

Imagine this graph:

        start
       /  |  \
      A   B   C
     /         \
    D           goal

DFS might explore:

start
↓
A
↓
D
↓
backtrack
↓
B
↓
C
↓
goal

---

3️⃣ DFS Mentality

DFS constantly thinks:

"Keep going deeper."

It prioritizes:

current branch exploration

before checking siblings.

---

4️⃣ Stack Behavior

DFS behaves like:

Stack

A stack works like:

Last In
First Out

This is called:

LIFO

---

Example

ADD A
ADD B
ADD C

Stack:

[A, B, C]

Remove:

C

because:

C was added last

---

5️⃣ Recursive Exploration

DFS is commonly implemented using:

recursion

---

Example

visit(node)
    ↓
visit(neighbor)
    ↓
visit(neighbor)

---

Recursion Flow

start
 ↓
A
 ↓
D
 ↓
end branch
 ↓
backtrack

---

6️⃣ Visual Example

Graph:

        start
       /     \
      A       B
     / \
    C   D

DFS exploration:

start
↓
A
↓
C
↓
backtrack
↓
D
↓
backtrack
↓
B

---

7️⃣ DFS Logic

Core Idea

Explore deeply before exploring widely.

---

Recursive Pseudo Code

FUNCTION dfs(node):

    mark node as visited

    FOR each neighbor:

        IF neighbor not visited:

            dfs(neighbor)

---

8️⃣ Visited Nodes

DFS MUST track visited nodes.

Otherwise:

infinite recursion

may happen.

---

Example Loop

A -> B
↑    ↓
D <- C

Without visited tracking:

A -> B -> C -> D -> A -> ...

forever 😄

---

Visited Example

visited = {
    "start",
    "A",
    "B"
}

---

9️⃣ Recursive Backtracking

When DFS reaches:

end of branch

it:

returns backwards

This is called:

backtracking

---

Visual Example

start
 ↓
A
 ↓
C
 ↓
no neighbors
 ↓
backtrack to A
 ↓
explore D

---

🔟 Iterative DFS

DFS can also be implemented without recursion.

Using:

stack

---

Iterative Pseudo Code

CREATE stack
CREATE visited set

PUSH start node

WHILE stack not empty:

    current = stack.pop()

    IF not visited:

        mark visited

        PUSH neighbors

---

1️⃣1️⃣ Complexity

DFS complexity is usually:

O(V + E)

Where:

V = vertices
E = edges

---

1️⃣2️⃣ DFS vs BFS

DFS

Explores:

deep first

---

BFS

Explores:

layer by layer

---

DFS Mentality

"Keep going deeper"

---

BFS Mentality

"Explore closest nodes first"

---

1️⃣3️⃣ DFS in Maze Generation

DFS is EXTREMELY popular for:

maze generation

Because:

DFS naturally creates long corridors

---

Example

Your A-Maze-ing project uses:

Randomized DFS

to:

• carve paths
• explore cells
• backtrack
• generate perfect mazes

---

DFS Maze Flow

current cell
    ↓
random neighbor
    ↓
carve wall
    ↓
continue deeper
    ↓
no neighbors?
    ↓
backtrack

---

1️⃣4️⃣ Fly-in Connection

DFS is useful in Fly-in for:

• graph traversal learning
• recursive exploration
• understanding pathfinding
• understanding backtracking

BUT:

DFS does NOT guarantee cheapest path

or:

shortest weighted route

That is why:

Dijkstra fits Fly-in better

---

1️⃣5️⃣ Mental Model

Think of DFS like:

exploring a cave

You:

• keep moving deeper
• follow one tunnel
• only return when stuck

---

Final Mental Image

DFS always asks:

"How far can I go from here?"

NOT:

"What is the closest node?"

That is the BIG difference between:

DFS
vs
BFS