Depth-First Search — Graph Algorithms

Overview

What this concept solves

Depth-First Search dives as deep as it can, then backs up. Start at a node. Pick the first child. Recurse. When you hit a dead-end — a node whose children are all visited — back up to the most recent node that still has unvisited children and continue. The trail you trace is a tree of 'first-time' edges, sometimes called the DFS tree.

Where BFS uses a queue and explores in rings, DFS uses a stack — usually the implicit call stack of recursion — and explores in branches. Two timestamps fall out of every visit: a discovery time when the node is first reached and pushed, and a finish time when its call returns and it's popped. Those, plus the edge classification DFS produces — tree edges (first-time discovery) versus back edges (an edge to a node still on the stack) — are the raw material for almost everything DFS is good at. A back edge is the textbook signature of a cycle.

That structure is the engine behind cycle detection (a back edge to a still-grey ancestor), topological sort (reverse post-order on a DAG), connected components, Tarjan SCC, and every backtracking solver from sudoku to maze. On a tree specifically — where there are no back edges — the only remaining choice is when you record a node relative to its children, and that single decision gives the three textbook orders: pre-order (record on the way down), in-order (between the children), and post-order (on the way back up). Same recursion as the graph walk; only the position of one record(node) line moves.

Mechanics

How it works

What DFS does on a graph

Start at a node, mark it grey (discovered, now on the stack), and record its discovery number.
Scan its neighbours in order. For each unseen neighbour, follow a tree edge and recurse — dive deeper before going wider.
If a neighbour is grey (still on the stack), that edge is a back edge — you've found a cycle. If it's black (finished), skip it.
When every neighbour is handled, the call returns: pop the frame, mark the node black (finished), record its finish number. That return is backtracking.

Why the call stack matters

Each recursive call pushes a frame on the stack — that's the 'grey' set in textbook DFS.
While a frame is on the stack, its node is in progress — its neighbours are being visited, but it isn't finished.
When the function returns, the frame pops — the node becomes 'black' (finished).
A back edge to a still-grey node = a cycle. Edges to black nodes = same component, no cycle.

On a tree: pre-, in-, and post-order

A tree has no back edges (no cycles), so the only freedom left is when you record a node relative to its children.
Pre-order (N L R) — record on the way down, at discovery time. Used to clone or serialise a tree.
In-order (L N R) — record between the two child recursions. On a BST this yields a sorted sequence.
Post-order (L R N) — record on the way back up, at finish time. Used to delete a tree or aggregate from the leaves up. Reverse post-order of a DAG is exactly a topological sort.

Recursion depth is a real problem

On a graph with a million nodes in a long path (think a linked list), recursive DFS blows the call stack. The fix is to write it iteratively with an explicit stack — same logic, no stack-overflow risk. Most production graph engines do this.

BFS vs DFS in one sentence

BFS asks 'who's nearby?' first — queue, level-order, shortest paths. DFS asks 'where does this go?' first — stack, recursion, structural questions. Same O(V + E) cost; entirely different output.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Depth-First Search

About this simulation

A seven-node graph with cycles — the same graph the BFS prototype uses — walked by recursive DFS. Press Play to watch it dive deep down one branch, then backtrack when a node's neighbours are all seen. Green lines are tree edges (first-time discovery); a dashed red line is a back edge — an edge to a node still on the call stack, which means a cycle. Use Step / Back to walk one call or return at a time, and Start to re-root the search.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Dive deep, then backtrack

Press Play from start A. Watch one branch go all the way down — A → B → C → E → D — before anything fans out. That's the stack at work: DFS commits to a path until it dead-ends. When a node's neighbours are all seen, its frame pops, the node turns green (finished), and the search backtracks to the previous node. Discovery order on this graph from A: A B C E D G F.

try 02

Spot the back edges (cycles)

Three dashed red edges appear — E–B, D–A, and F–C. Each is an edge to a node still on the call stack, which is the signature of a cycle. The back edges counter climbs to 3. The 6 green tree edges plus these 3 back edges account for all 9 edges the search touches. On an acyclic graph (a tree) this counter would stay at 0.

try 03

Read the call stack

The left lane is the live call stack, top frame marked running. Step through and watch it grow as DFS descends and shrink as each dfs() returns. Its maximum height is the longest root-to-leaf path the search explored — the recursion depth that would overflow a real stack on a very deep graph.

try 04

Re-root the search

Pick a different Start node. The discovery order and which edges become tree vs back edges both change — but the graph's node set and its underlying cycles don't. DFS structure depends on where you start and the neighbour order; the graph itself is fixed.

In practice

When to use it — and what you give up

When it's the right tool

Tree traversal — pre/in/post-order is DFS with record() in a different spot. Every tree walk is one of these three.
Cycle detection — the back-edge test fires the moment you see a grey-to-grey transition.
Topological sort — reverse post-order of a DAG-DFS is a valid topo order. No extra code needed.
Connected components — one DFS sweep from each unvisited node; everything it touches is one component.
Strongly connected components — Tarjan's and Kosaraju's algorithms are both two DFS passes with light bookkeeping.
Backtracking problems — maze solving, sudoku, N-queens, generating permutations. 'Undo on failure' is just popping the recursion stack.

When to reach for something else

Shortest path in an unweighted graph — use BFS. DFS doesn't track distances and will happily report a long path before the short one.
Weighted shortest path — use Dijkstra. DFS visit-order has nothing to do with cost.
Very deep graphs — write DFS iteratively or use BFS; recursive DFS overflows the call stack at a few hundred thousand nodes.

Pros

Linear time — O(V + E), same as BFS. Visits every node and edge once.
One function, three orders — pre/in/post-order all share the recursion, differing only by where record() sits.
Discovers structure — tree edges, back edges, discovery/finish times — the inputs to Tarjan SCC, articulation points, bridges.
Low memory on narrow graphs — only needs to remember the current path: O(depth) instead of O(width).
The native shape of backtracking — try a choice, recurse, undo on failure. Every backtracking solver is DFS in disguise.

Cons

No shortest-path guarantee — DFS can find any path before the shortest one. Use BFS or Dijkstra if distance matters.
Stack overflow on deep graphs — recursive form fails at ~1e5 nodes deep in many runtimes; switch to an explicit stack.
Visit order depends on child order — same tree stored differently produces different traversals. Surprising for tests.
Pre/in/post are tree concepts — on general graphs you only get pre-order (discovery time) and post-order (finish time); in-order needs a notion of 'middle child' which only exists on binary trees.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

dfs-graph.ts

// Recursive DFS on a graph (adjacency list). Records discovery /
// finish order and classifies each edge as a tree or back edge.
type Color = "white" | "grey" | "black";

function dfs(adj: Map<string, string[]>, start: string) {
  const color = new Map<string, Color>();   // white = unseen, grey = on stack, black = done
  const order: string[] = [];               // discovery order
  const backEdges: [string, string][] = []; // each one closes a cycle
  let time = 0;
  const disc = new Map<string, number>();
  const fin = new Map<string, number>();

  function visit(u: string, parent: string | null) {
    color.set(u, "grey");                    // push: discovered, now on the stack
    disc.set(u, ++time);
    order.push(u);

    for (const v of adj.get(u) ?? []) {
      if (v === parent) continue;            // skip the undirected edge we arrived on
      const c = color.get(v) ?? "white";
      if (c === "white") {
        visit(v, u);                         // tree edge — recurse deeper
      } else if (c === "grey") {
        backEdges.push([u, v]);              // back edge → cycle
      }
      // black: already finished — nothing to do
    }

    color.set(u, "black");                   // pop: this frame returns, node finished
    fin.set(u, ++time);
  }

  visit(start, null);
  return { order, backEdges, disc, fin };
}

// disc = pre-order (discovery) time; fin = post-order (finish) time.
// Reverse the nodes by finish time and you have a topological sort of a DAG.
// On a graph millions of nodes deep, rewrite this with an explicit stack.

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. Sign in to save your best score.

question 01 / 03

BFS and DFS both visit every node in O(V + E). What is the essential difference in how they explore a graph?

question 02 / 03

Using the white-grey-black classification on a graph DFS, what indicates a cycle?

question 03 / 03

After a DFS over a directed acyclic graph (DAG), how do you read off a valid topological order?

0/3 answered