Depth-First Search (DFS) — Dive Deep First, Then Backtrack

Shreyas Naphad
Jul 4
1 min read

Ever gone into a maze and kept turning left until you hit a wall, then backtracked to try another path? That’s exactly how Depth-First Search (DFS) works.

DFS is a graph traversal algorithm that explores as far as possible along each path before backtracking. It's like going deep into one branch before checking others.

🔍 What’s the Goal?

To visit every node in a graph (or tree), one path at a time — diving deep before turning back.

🛠️ How It Works

Start at any node.
Visit it and mark it as visited.
Go to the first unvisited neighbor.
Repeat the process.
If no unvisited neighbors are left, backtrack.
Continue until all nodes are visited.

You can do this using recursion or a stack.

🧠 Analogy

Imagine exploring a cave. You take one tunnel and keep going deeper until you hit a dead end. Then, you come back and try a different tunnel. You go deep before wide.

📍 Where It's Used

Solving puzzles like mazes
Topological sorting
Detecting cycles in graphs
Finding connected components
Building AI for decision-making in games

    A
    / \
   B   C
  /     \
 D       E

DFS from A →

A → B → D → (backtrack) → C → E

✅ Final Thought

DFS is like a curious adventurer 🧗‍♂️ — always choosing to go deep and explore to the end before checking out the other paths.