Depth-First Search (DFS) works like exploring a maze with a spool of string! It dives as deep as possible down a single path before backtracking when hitting a dead end.
How it Works Step-by-Step:
1Dive Deep Down One Path: Start at the root node and pick an unexplored branch. Keep walking down that same path without turning back!
2Hit a Dead End: When you reach a room with no new unvisited tunnels, stop.
3Backtrack (Retrace Steps): Rewind your string backward to the previous room in your Call Stack until you find an unexplored side tunnel.
4Repeat Until Done: Explore every side tunnel until all nodes have been visited!
Imagine exploring an underground cave network. You follow the leftmost tunnel as deep into the earth as it goes. When you hit a solid rock wall (dead end), you retrace your steps backward to the last intersection and try the right tunnel!