Skip to content
Back to AlgorithmsAll lessons

Algorithms

Depth-First Search (DFS)

O(V + E) time — every point and connection is visited once · up to O(V) space for the recursion stack, the memory used to track calls waiting to finish.

The idea, in plain English

Depth-first search (DFS) explores a maze by always going as deep as possible down one path before it backs up. Pick a direction, keep walking until you hit a dead end, then step back to the last fork and try another way.

How it works

  1. 1Visit the starting point and mark it as visited.
  2. 2Go to its first unvisited neighbor, then that neighbor's first unvisited neighbor. Keep diving deeper.
  3. 3When you hit a dead end, back up to the last spot with an unexplored path and continue.

When you'd use it

Use it to explore every possibility, such as solving a maze or puzzle, to find cycles, or to walk through a tree or folder structure from top to bottom.

Common beginner mistakes

  • Forgetting to track visited points, so it loops forever when there is a cycle.
  • Running out of stack space from recursion on a very deep or huge graph.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
DFS from A: A B D E F C

Note: In Python, avoid a mutable default value like order=[]. This is a classic trap: it shares one list across every call instead of starting fresh. We use None instead, and create a new list each time.

See it in motion

Watch it traverseDepth-first searchfrom AO(V + E) time — every point and connection is visited once · up to O(V) space for the recursion stack, the memory used to track calls waiting to finish.
ABCDEF
Stack (LIFO)next out: top ↦
A
Visit order
A

Start at A and dive in.

1/6
Visited
1
On stack
1/13
Step
0.0s
Time
Visiting nowOn stackDoneUnvisited

Not sure this is the right topic? See the learning paths → or where this leads →