Depth First Search (DFS) explores as deep as possible before backtracking. Think of solving a maze by sticking to the left wall continually.
We begin at 'A'. We add it to our Stack (to remember where we are) and mark it as visited.
From 'A', we choose the first neighbor 'B'. We push 'B' onto the stack and visit it.
From 'B', we go to 'D'. We are now at a dead end (Leaf node).
No more neighbors at 'D'. We pop 'D' off the stack and return to 'B'.
Back at 'B', we see another neighbor 'E'. Let's visit it.
E is a dead end. Backtrack to B. B is done. Backtrack to A.
Finally, we explore 'A's other neighbor: 'C'.
From 'C', we visit 'F'. All nodes visited!
DFS visits every Vertex and Edge. It's powerful for finding paths, cycles, and solving puzzles.
DFS uses a Stack to dive deep. What happens if we use a Queue instead?