Ready to go deep? Depth-First Search (DFS) is one of the most beloved algorithms in all of computer science, and once it clicks, graphs stop feeling scary and start feeling like playgrounds. 🤿

DFS is a graph traversal strategy where you pick a start node, charge down one branch as far as you can, and only when you hit a dead end do you backtrack and try the next path. It's the algorithmic version of "go deep first, ask questions later" — exactly right for solving mazes, scheduling tasks, parsing nested structures, hunting cycles, and crawling deeply linked sites. Whenever the path itself matters more than how many nodes you touch, DFS is the tool you reach for.

Big idea: BFS asks "what's near me?" — DFS asks "how far can I go down this road?"

How DFS Works

Let's walk through it on a small graph:

    A
   / \
  B   C
 / \   \
D   E - F

Starting at A, DFS picks one neighbour (say B), goes to B, then dives further to D. D has no unvisited neighbours, so we backtrack to B and try its next child, E. From E we slide over to F. F has no new neighbours, so we backtrack all the way up to A, and finally visit C (whose only neighbour F is already visited). Final order: A → B → D → E → F → C.

The pattern is always the same:

1. Mark the current node as visited.

2. For each unvisited neighbour, recurse (or push onto a stack).

3. When you run out of neighbours, return — that's the backtrack.

The visited set is non-negotiable on a real graph. Without it, any cycle becomes an infinite loop. 😅

Recursive vs Iterative DFS

Two flavours of DFS in Python, same algorithm wearing different clothes:

Recursive DFS uses Python's call stack implicitly. Short, elegant, reads like the definition. The catch: Python's default recursion limit is 1000 (sys.getrecursionlimit()), so a chain of 1500 nodes blows up with RecursionError. You can bump it with sys.setrecursionlimit(...), but the C stack is finite — don't go wild.

Iterative DFS uses an explicit list as a stack — append to push, pop to pop. No recursion limit, no overflow, identical results if you order neighbours carefully.

Pick recursion for trees, small graphs, and readable code. Pick iteration for production, very deep graphs, or anything user-facing where RecursionError would be embarrassing.

Pre-order, In-order, Post-order in DFS

These terms come from binary trees but they generalise to graphs as when you record the node:

Pre-order: record the node before recursing — useful for copying structures or printing hierarchies.

In-order: record between left and right children. Tree-only — gives sorted output on a BST.

Post-order: record after all children visited. This is the secret sauce behind topological sort — reverse the post-order and you get a valid linear ordering of a DAG.

On graphs, pre-order tells you when nodes were discovered; post-order tells you when they were finished. That finish-order is what makes DFS so powerful for dependency resolution.

Complexity Analysis

Resource	Cost	Why
Time	O(V + E)	Every vertex marked once, every edge inspected once
Space (visited set)	O(V)	One entry per node
Space (recursion / explicit stack)	O(V) worst case	A long thin path forces every node onto the stack

So DFS is linear in the size of the graph — you can't do meaningful traversal faster than that.

DFS vs BFS

DFS	BFS
Strategy	Go deep, then backtrack	Visit all neighbours first
Data structure	Stack (or recursion)	Queue (`collections.deque`)
Shortest path on unweighted graph?	❌ No	✅ Yes
Memory profile	O(text{depth}) — friendly on wide graphs	O(text{width}) — can balloon on bushy graphs
Best for	Cycles, topo sort, backtracking, components	Shortest path, level-order, peer discovery

If you need the shortest number of hops, use BFS. If you need to enumerate paths, detect cycles, or order dependencies — that's recursive DFS (or iterative) territory.

Common Pitfalls

Hitting the recursion limit. Default ~1000. On deep graphs, switch to iterative or bump the limit carefully.

Forgetting `visited` on a cyclic graph. Tree DFS doesn't need one (no cycles), but on a graph, omitting it = infinite loop.

Mutating the graph during traversal. Adding or removing edges mid-DFS breaks invariants and double-visits nodes.

Confusing tree DFS with graph DFS. They look identical, but graph DFS must track visited nodes.

Wrong child ordering. Iterative DFS often reversed()s neighbours so the leftmost ends up on top of the stack — match this if you want both versions to agree.

Using DFS for shortest path. It finds a path, not the shortest. Use BFS or Dijkstra instead.

Real-World Uses

Topological sort — build systems (Make, Bazel), task schedulers, course prerequisites.

Cycle detection — deadlocks, dependency loops in package managers.

Strongly connected components — Tarjan's and Kosaraju's algorithms both ride on DFS.

Maze solving and pathfinding — DFS with backtracking is the natural fit.

Backtracking puzzles — Sudoku, N-queens, crossword solvers.

Parsing recursive grammars — compilers walk ASTs depth-first.

Articulation points and bridges — finding critical nodes/edges in a network.

Web spider crawling — depth-first crawlers explore one site fully before moving on.

DFS Variants

Iterative Deepening DFS (IDDFS) runs depth-limited DFS at depth 1, then 2, then 3, and so on. Time is still O(b^d) like BFS, but space drops to O(d) — you get BFS's optimality with DFS's tiny memory footprint. Game AI loves this.

Bidirectional DFS searches forward from the start and backward from the goal at once, meeting in the middle to slash the search space.

Randomised DFS — shuffle neighbours before recursing. The classic way to generate beautifully unpredictable mazes.

Frequently Asked Questions

Can DFS find the shortest path? Not on a general graph — it finds a path. Use BFS for unweighted, Dijkstra or A* for weighted.

How do I avoid stack overflow? Use the iterative version with an explicit list-as-stack, or call sys.setrecursionlimit(10_000) for moderate increases.

Iterative vs recursive — which is faster? Same Big-O. Iterative is often slightly faster in Python (no function-call overhead), but the gap is small. Choose for clarity, not micro-speed.

Why is DFS used for topological sort? The post-order finish time of DFS on a DAG, reversed, is a valid topological ordering. No other traversal gives you that for free.

Can DFS detect cycles? Yes — track nodes in three states (unvisited, in-progress, done). Hitting an in-progress node means you found a back-edge — a cycle.

Difference between DFS and backtracking? Backtracking is DFS over a search tree of decisions, plus pruning. Every backtracking algorithm — Sudoku, N-queens, CSPs — is a DFS in disguise.

Have fun tracing the paths your depth-first search takes — once DFS clicks, you'll spot it everywhere. 🎉

Depth-First Search (DFS) in Python

Try it yourself

How it works