Depth-First Search: The Algorithm That Explores Like a Maze Walker

Introduction

Imagine you are in a maze holding a piece of chalk. A simple strategy always gets you through: keep walking into corridors you have not tried yet; when you hit a dead end, walk back to the last junction that still has an untried corridor, and try that one. Mark what you have already explored so you never repeat it.

That is depth-first search (DFS). Applied to any graph — a road map, a web of package dependencies, the states of a puzzle — it always extends the most recent path as far as it can go, and only backtracks when every edge out of the current node has been examined. Its sibling, breadth-first search, does the opposite: it explores in rings of increasing distance, using a queue instead of a stack.

The maze version is old. The French engineer Charles Pierre Trémaux devised a chalk-marking method for escaping labyrinths in the 19th century, and Édouard Lucas published it in the first volume of his Récréations mathématiques (1882). What turned this folk technique into one of the most important ideas in computer science was the work of John Hopcroft and Robert Tarjan in the early 1970s: they showed that the order in which DFS discovers and abandons nodes carries enough structure to solve a whole family of graph problems in linear time.

The algorithm fits in a few lines. Each node is coloured white (unseen), grey (discovered, still on the stack) or black (finished), and receives two timestamps — a discovery time d and a finish time f:

DFS(G):
    for each vertex u:  color[u] = WHITE
    time = 0
    for each vertex u:
        if color[u] == WHITE:  VISIT(u)

VISIT(u):
    time = time + 1;  d[u] = time;  color[u] = GREY
    for each edge (u, v):
        if color[v] == WHITE:  VISIT(v)        # tree edge
        elif color[v] == GREY: report cycle    # back edge
    color[u] = BLACK
    time = time + 1;  f[u] = time

The recursion is the stack: the chain of active calls is exactly the path from the root of the search to the node being explored.

Try It

Pick a graph and press Step to advance the search one action at a time: starting a tree, inspecting one edge, or finishing one node. Run animates the whole thing. Neighbours are always tried in alphabetical order.

<p class="hint">Depth-first search dives along one edge after another and backtracks only when it gets stuck. Each node shows <b>discovery/finish</b> times; each edge is coloured by its type as soon as the search inspects it.</p>
<div class="bar">
  <label for="preset">Graph:</label>
  <select id="preset">
    <option value="dag">Acyclic (DAG)</option>
    <option value="cycle">With a cycle</option>
    <option value="maze">Maze (undirected)</option>
  </select>
</div>
<svg id="g" viewBox="0 0 350 248" role="img" aria-label="Graph being explored by depth-first search"></svg>
<div class="stackrow">
  <span class="lab">Stack (bottom → top):</span>
  <span id="stack" class="stack"></span>
  <span id="clock" class="clock"></span>
</div>
<div id="status" class="status">Press Step to begin at node A, or Run to animate.</div>
<div id="result" class="result"></div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span><i class="sw tree"></i>tree</span>
  <span><i class="sw back"></i>back</span>
  <span><i class="sw forward"></i>forward</span>
  <span><i class="sw cross"></i>cross</span>
  <span><i class="dot white"></i>unvisited</span>
  <span><i class="dot grey"></i>on the stack</span>
  <span><i class="dot black"></i>finished</span>
</div>

/* Colour tokens for light and dark mode; edge colours encode the edge type. */
:root { --fg: #1f2937; --muted: #4b5563; --bg: #ffffff; --panel: #f1f5f9; --line: #cbd5e1;
        --unseen: #a3adb9; --tree: #2563eb; --back: #dc2626; --forward: #16a34a; --cross: #d97706;
        --nwhite: #ffffff; --ngrey: #9ca3af; --nblack: #111827; --nstroke: #334155; --btn: #1d3557; --btnfg: #ffffff; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e5e7eb; --muted: #9ca3af; --bg: #111827; --panel: #1f2937; --line: #374151;
          --unseen: #4b5563; --tree: #60a5fa; --back: #f87171; --forward: #4ade80; --cross: #fbbf24;
          --nwhite: #f8fafc; --ngrey: #6b7280; --nblack: #020617; --nstroke: #cbd5e1; --btn: #93c5fd; --btnfg: #0b1220; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.bar { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .3rem; font-size: .9rem; }
select { font: 14px system-ui, sans-serif; padding: .3rem .4rem; border-radius: 6px; border: 1px solid var(--line);
         background: var(--panel); color: var(--fg); max-width: 100%; }
svg { width: 100%; max-width: 520px; height: auto; display: block; background: var(--panel); border-radius: 10px; }
.edge { stroke: var(--unseen); stroke-width: 2; fill: none; transition: stroke .2s; }
.edge.tree { stroke: var(--tree); stroke-width: 3.2; }
.edge.back { stroke: var(--back); stroke-width: 3; stroke-dasharray: 6 4; }
.edge.forward { stroke: var(--forward); stroke-width: 2.6; stroke-dasharray: 2 4; }
.edge.cross { stroke: var(--cross); stroke-width: 2.6; stroke-dasharray: 9 3 2 3; }
.edge.cur { stroke-width: 5; }
.mk-unseen { fill: var(--unseen); } .mk-tree { fill: var(--tree); } .mk-back { fill: var(--back); }
.mk-forward { fill: var(--forward); } .mk-cross { fill: var(--cross); }
.node circle { stroke: var(--nstroke); stroke-width: 2; transition: fill .2s; }
.node.white circle { fill: var(--nwhite); }
.node.grey circle { fill: var(--ngrey); }
.node.black circle { fill: var(--nblack); }
.node.top circle { stroke: var(--tree); stroke-width: 4; }
.node .nm { font: 700 14px system-ui, sans-serif; text-anchor: middle; dominant-baseline: central; fill: #111827; }
.node.black .nm { fill: #f8fafc; }
.node .tm { font: 600 11px ui-monospace, monospace; text-anchor: middle; fill: var(--fg); }
.stackrow { display: flex; align-items: center; gap: .35rem; flex-wrap: wrap; margin: .45rem 0 .2rem; font-size: .85rem; }
.lab { font-weight: 700; }
.stack { display: inline-flex; gap: 3px; flex-wrap: wrap; min-height: 1.6em; }
.chip { display: inline-block; min-width: 1.6em; text-align: center; padding: .1rem .35rem; border-radius: 5px;
        background: var(--ngrey); color: #111827; font: 700 13px ui-monospace, monospace; }
.chip.top { outline: 2px solid var(--tree); }
.chip.none { background: transparent; color: var(--muted); font-weight: 400; }
.clock { margin-left: auto; color: var(--muted); font-family: ui-monospace, monospace; }
.status { font-size: .92rem; font-weight: 600; margin: .3rem 0; min-height: 2.7em; line-height: 1.35; }
.status.bad { color: var(--back); }
.status.ok { color: var(--forward); }
.result { font-size: .9rem; min-height: 1.3em; margin-bottom: .4rem; font-weight: 600; }
.result.bad { color: var(--back); }
.result.ok { color: var(--forward); }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--btn);
         background: var(--btn); color: var(--btnfg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--btn); }
button:disabled { opacity: .45; cursor: default; }
.legend { display: flex; flex-wrap: wrap; gap: .3rem .8rem; margin-top: .6rem; font-size: .78rem; color: var(--muted); }
.legend span { display: inline-flex; align-items: center; gap: .3rem; }
.sw { display: inline-block; width: 22px; height: 0; border-top: 3px solid; }
.sw.tree { border-color: var(--tree); } .sw.back { border-color: var(--back); border-top-style: dashed; }
.sw.forward { border-color: var(--forward); border-top-style: dotted; } .sw.cross { border-color: var(--cross); border-top-style: dashed; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; border: 1.5px solid var(--nstroke); }
.dot.white { background: var(--nwhite); } .dot.grey { background: var(--ngrey); } .dot.black { background: var(--nblack); }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Three small graphs. Neighbours are visited in alphabetical order so every run is reproducible.
const PRESETS = {
  dag: { undirected: false,
    nodes: { A: [40, 40], B: [130, 40], D: [220, 40], G: [310, 40], C: [40, 125], E: [130, 125], H: [220, 125], I: [310, 125], F: [130, 205] },
    edges: ['AB', 'AC', 'AE', 'BD', 'BE', 'DG', 'EG', 'EH', 'CE', 'CF', 'FH', 'HI', 'GI'] },
  cycle: { undirected: false,
    nodes: { A: [40, 40], B: [130, 40], D: [220, 40], G: [310, 40], C: [40, 125], E: [130, 125], H: [220, 125], I: [310, 125], F: [130, 205] },
    edges: ['AB', 'AC', 'AE', 'BD', 'BE', 'DG', 'EG', 'EH', 'CE', 'CF', 'FH', 'HI', 'GI', 'HB'] },
  maze: { undirected: true,
    nodes: { A: [60, 40], B: [175, 40], C: [290, 40], D: [60, 125], E: [175, 125], F: [290, 125], G: [60, 205], H: [175, 205], I: [290, 205] },
    edges: ['AB', 'AD', 'BC', 'CF', 'DG', 'GH', 'HI', 'HE', 'EB'] }
};

// Iterative DFS with an explicit stack of frames (node, next-neighbour index). Each call to step() does exactly one thing: start a tree, inspect one edge, or finish one node.
function makeDFS(G) {
  const names = Object.keys(G.nodes).sort();
  const adj = {};
  names.forEach(n => { adj[n] = []; });
  G.edges.forEach((e, id) => {
    adj[e[0]].push({ v: e[1], id });
    if (G.undirected) adj[e[1]].push({ v: e[0], id });
  });
  names.forEach(n => adj[n].sort((a, b) => (a.v < b.v ? -1 : a.v > b.v ? 1 : a.id - b.id)));
  const S = { names, adj, color: {}, d: {}, f: {}, kind: {}, stack: [], time: 0, finished: [], backEdges: [], done: false, cur: null };
  names.forEach(n => { S.color[n] = 'white'; });
  // A frame remembers which neighbour to try next, so we never push the same node twice.
  function discover(u, pe) { S.d[u] = ++S.time; S.color[u] = 'grey'; S.stack.push({ u, i: 0, pe }); }
  S.step = function () {
    S.cur = null;
    if (S.done) return { type: 'done' };
    if (!S.stack.length) {
      const r = names.find(n => S.color[n] === 'white');
      if (r === undefined) { S.done = true; return { type: 'done' }; }
      discover(r, -1);
      return { type: 'start', u: r, d: S.d[r] };
    }
    const fr = S.stack[S.stack.length - 1];
    const u = fr.u;
    if (fr.i < adj[u].length) {
      const { v, id } = adj[u][fr.i++];
      S.cur = id;
      // Undirected graphs: the edge back to the parent and edges already seen from the other end are not new edges.
      if (G.undirected && id === fr.pe) return { type: 'parent', u, v, id };
      if (G.undirected && S.kind[id]) return { type: 'seen', u, v, id };
      // White = tree edge, grey = back edge (cycle), black = forward if v was discovered after u, otherwise cross.
      const c = S.color[v];
      if (c === 'white') { S.kind[id] = 'tree'; discover(v, id); return { type: 'tree', u, v, id, d: S.d[v] }; }
      if (c === 'grey') { S.kind[id] = 'back'; S.backEdges.push(id); return { type: 'back', u, v, id }; }
      const k = S.d[u] < S.d[v] ? 'forward' : 'cross';
      S.kind[id] = k;
      return { type: k, u, v, id };
    }
    // No neighbours left: assign the finish time, colour the node black and pop it (backtrack).
    S.stack.pop();
    S.f[u] = ++S.time;
    S.color[u] = 'black';
    S.finished.push(u);
    return { type: 'finish', u, f: S.f[u] };
  };
  return S;
}

const NS = 'http://www.w3.org/2000/svg';
const R = 15;
const svg = document.getElementById('g');
const presetSel = document.getElementById('preset');
const statusEl = document.getElementById('status');
const resultEl = document.getElementById('result');
const runBtn = document.getElementById('run');
const stepBtn = document.getElementById('step');
let G = PRESETS.dag, S = null, timer = null;

function el(tag, attrs, parent) {
  const e = document.createElementNS(NS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  if (parent) parent.appendChild(e);
  return e;
}
const sep = () => (G.undirected ? '–' : '→');
const edgeText = (id) => G.edges[id][0] + sep() + G.edges[id][1];

// Draw edges, then nodes with their discovery/finish stamps, then the stack.
function render() {
  svg.innerHTML = '';
  const defs = el('defs', {}, svg);
  ['unseen', 'tree', 'back', 'forward', 'cross'].forEach(k => {
    const m = el('marker', { id: 'm-' + k, viewBox: '0 0 10 10', refX: '9', refY: '5', markerWidth: '6', markerHeight: '6', orient: 'auto-start-reverse' }, defs);
    el('path', { d: 'M0,0 L10,5 L0,10 z', class: 'mk-' + k }, m);
  });
  const top = S.stack.length ? S.stack[S.stack.length - 1].u : null;
  G.edges.forEach((e, id) => {
    const [x1, y1] = G.nodes[e[0]], [x2, y2] = G.nodes[e[1]];
    const len = Math.hypot(x2 - x1, y2 - y1), ux = (x2 - x1) / len, uy = (y2 - y1) / len;
    // Trim each line so it stops at the circle border (and leaves room for the arrowhead).
    const pad = G.undirected ? R : R + 2;
    const k = S.kind[id] || 'unseen';
    const attrs = { x1: x1 + ux * R, y1: y1 + uy * R, x2: x2 - ux * pad, y2: y2 - uy * pad,
      class: 'edge ' + k + (S.cur === id ? ' cur' : '') };
    if (!G.undirected) attrs['marker-end'] = 'url(#m-' + k + ')';
    el('line', attrs, svg);
  });
  S.names.forEach(n => {
    const [x, y] = G.nodes[n];
    const g = el('g', { class: 'node ' + S.color[n] + (n === top ? ' top' : '') }, svg);
    el('circle', { cx: x, cy: y, r: R }, g);
    el('text', { x, y, class: 'nm' }, g).textContent = n;
    if (S.d[n]) el('text', { x, y: y + R + 13, class: 'tm' }, g).textContent = S.d[n] + '/' + (S.f[n] || '·');
  });
  const st = document.getElementById('stack');
  st.innerHTML = '';
  if (!S.stack.length) {
    const c = document.createElement('span'); c.className = 'chip none'; c.textContent = "empty"; st.appendChild(c);
  }
  S.stack.forEach((fr, i) => {
    const c = document.createElement('span');
    c.className = 'chip' + (i === S.stack.length - 1 ? ' top' : '');
    c.textContent = fr.u; st.appendChild(c);
  });
  document.getElementById('clock').textContent = i18nFmt("time = %t%", { t: S.time });
}

function say(text, cls) { statusEl.textContent = text; statusEl.className = 'status ' + (cls || ''); }

function describe(ev) {
  const e = ev.id !== undefined ? edgeText(ev.id) : '';
  const p = { e, u: ev.u, v: ev.v, d: ev.d, f: ev.f };
  switch (ev.type) {
    case 'start': return [i18nFmt("The stack is empty — start a new DFS tree at %u% (d = %d%).", p), ''];
    case 'tree': return [i18nFmt("%e%: %v% is white → tree edge. Go deeper (d = %d%).", p), ''];
    case 'back': return [i18nFmt("%e%: %v% is grey, still on the stack → back edge. Cycle found!", p), 'bad'];
    case 'forward': return [i18nFmt("%e%: %v% is black and a descendant of %u% → forward edge.", p), ''];
    case 'cross': return [i18nFmt("%e%: %v% is black in a branch that already finished → cross edge.", p), ''];
    case 'parent': return [i18nFmt("%e%: the corridor we just came through — skip it.", p), ''];
    case 'seen': return [i18nFmt("%e%: already classified from the other end — skip it.", p), ''];
    case 'finish': return [i18nFmt("%u% has no unexplored edges → finish it (f = %f%) and backtrack.", p), ''];
  }
  return ['', ''];
}

function showResult() {
  if (S.done) {
    if (G.undirected) {
      resultEl.textContent = i18nFmt("Every cell reached. The blue tree edges form a spanning tree of the maze; back edges closing a loop: %n%.", { n: S.backEdges.length });
      resultEl.className = 'result ok';
    } else if (S.backEdges.length) {
      resultEl.textContent = i18nFmt("Back edge %e% closes a cycle, so no topological order exists.", { e: edgeText(S.backEdges[0]) });
      resultEl.className = 'result bad';
    } else {
      resultEl.textContent = i18nFmt("No back edge, so this is a DAG. Topological order (reverse finish times): %order%", { order: S.finished.slice().reverse().join(' ') });
      resultEl.className = 'result ok';
    }
  } else if (S.backEdges.length) {
    resultEl.textContent = G.undirected ? "⟲ Loop found (a back edge)" : "⟲ Cycle found (a back edge)";
    resultEl.className = 'result bad';
  } else {
    resultEl.textContent = '';
    resultEl.className = 'result';
  }
}

function step() {
  const ev = S.step();
  if (ev.type === 'done') { stop(); say("Search complete: every node is black.", 'ok'); stepBtn.disabled = true; runBtn.disabled = true; }
  else { const [t, c] = describe(ev); say(t, c); }
  render();
  showResult();
}

function stop() { if (timer) { clearInterval(timer); timer = null; } runBtn.textContent = "Run"; }

// Run calls step() on a timer until the search is done.
function toggleRun() {
  if (timer) { stop(); return; }
  runBtn.textContent = "Pause";
  timer = setInterval(step, 650);
  step();
}

function reset() {
  stop();
  G = PRESETS[presetSel.value] || PRESETS.dag;
  S = makeDFS(G);
  stepBtn.disabled = false; runBtn.disabled = false;
  say("Press Step to begin at node A, or Run to animate.", '');
  render();
  showResult();
}

stepBtn.addEventListener('click', () => { stop(); step(); });
runBtn.addEventListener('click', toggleRun);
document.getElementById('reset').addEventListener('click', reset);
presetSel.addEventListener('change', reset);
reset();

<p class="hint">Depth-first search dives along one edge after another and backtracks only when it gets stuck. Each node shows <b>discovery/finish</b> times; each edge is coloured by its type as soon as the search inspects it.</p>
<div class="bar">
  <label for="preset">Graph:</label>
  <select id="preset">
    <option value="dag">Acyclic (DAG)</option>
    <option value="cycle">With a cycle</option>
    <option value="maze">Maze (undirected)</option>
  </select>
</div>
<svg id="g" viewBox="0 0 350 248" role="img" aria-label="Graph being explored by depth-first search"></svg>
<div class="stackrow">
  <span class="lab">Stack (bottom → top):</span>
  <span id="stack" class="stack"></span>
  <span id="clock" class="clock"></span>
</div>
<div id="status" class="status">Press Step to begin at node A, or Run to animate.</div>
<div id="result" class="result"></div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span><i class="sw tree"></i>tree</span>
  <span><i class="sw back"></i>back</span>
  <span><i class="sw forward"></i>forward</span>
  <span><i class="sw cross"></i>cross</span>
  <span><i class="dot white"></i>unvisited</span>
  <span><i class="dot grey"></i>on the stack</span>
  <span><i class="dot black"></i>finished</span>
</div>

/* Colour tokens for light and dark mode; edge colours encode the edge type. */
:root { --fg: #1f2937; --muted: #4b5563; --bg: #ffffff; --panel: #f1f5f9; --line: #cbd5e1;
        --unseen: #a3adb9; --tree: #2563eb; --back: #dc2626; --forward: #16a34a; --cross: #d97706;
        --nwhite: #ffffff; --ngrey: #9ca3af; --nblack: #111827; --nstroke: #334155; --btn: #1d3557; --btnfg: #ffffff; }
@media (prefers-color-scheme: dark) {
  :root { --fg: #e5e7eb; --muted: #9ca3af; --bg: #111827; --panel: #1f2937; --line: #374151;
          --unseen: #4b5563; --tree: #60a5fa; --back: #f87171; --forward: #4ade80; --cross: #fbbf24;
          --nwhite: #f8fafc; --ngrey: #6b7280; --nblack: #020617; --nstroke: #cbd5e1; --btn: #93c5fd; --btnfg: #0b1220; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; }
.hint { font-size: .88rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.bar { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .3rem; font-size: .9rem; }
select { font: 14px system-ui, sans-serif; padding: .3rem .4rem; border-radius: 6px; border: 1px solid var(--line);
         background: var(--panel); color: var(--fg); max-width: 100%; }
svg { width: 100%; max-width: 520px; height: auto; display: block; background: var(--panel); border-radius: 10px; }
.edge { stroke: var(--unseen); stroke-width: 2; fill: none; transition: stroke .2s; }
.edge.tree { stroke: var(--tree); stroke-width: 3.2; }
.edge.back { stroke: var(--back); stroke-width: 3; stroke-dasharray: 6 4; }
.edge.forward { stroke: var(--forward); stroke-width: 2.6; stroke-dasharray: 2 4; }
.edge.cross { stroke: var(--cross); stroke-width: 2.6; stroke-dasharray: 9 3 2 3; }
.edge.cur { stroke-width: 5; }
.mk-unseen { fill: var(--unseen); } .mk-tree { fill: var(--tree); } .mk-back { fill: var(--back); }
.mk-forward { fill: var(--forward); } .mk-cross { fill: var(--cross); }
.node circle { stroke: var(--nstroke); stroke-width: 2; transition: fill .2s; }
.node.white circle { fill: var(--nwhite); }
.node.grey circle { fill: var(--ngrey); }
.node.black circle { fill: var(--nblack); }
.node.top circle { stroke: var(--tree); stroke-width: 4; }
.node .nm { font: 700 14px system-ui, sans-serif; text-anchor: middle; dominant-baseline: central; fill: #111827; }
.node.black .nm { fill: #f8fafc; }
.node .tm { font: 600 11px ui-monospace, monospace; text-anchor: middle; fill: var(--fg); }
.stackrow { display: flex; align-items: center; gap: .35rem; flex-wrap: wrap; margin: .45rem 0 .2rem; font-size: .85rem; }
.lab { font-weight: 700; }
.stack { display: inline-flex; gap: 3px; flex-wrap: wrap; min-height: 1.6em; }
.chip { display: inline-block; min-width: 1.6em; text-align: center; padding: .1rem .35rem; border-radius: 5px;
        background: var(--ngrey); color: #111827; font: 700 13px ui-monospace, monospace; }
.chip.top { outline: 2px solid var(--tree); }
.chip.none { background: transparent; color: var(--muted); font-weight: 400; }
.clock { margin-left: auto; color: var(--muted); font-family: ui-monospace, monospace; }
.status { font-size: .92rem; font-weight: 600; margin: .3rem 0; min-height: 2.7em; line-height: 1.35; }
.status.bad { color: var(--back); }
.status.ok { color: var(--forward); }
.result { font-size: .9rem; min-height: 1.3em; margin-bottom: .4rem; font-weight: 600; }
.result.bad { color: var(--back); }
.result.ok { color: var(--forward); }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid var(--btn);
         background: var(--btn); color: var(--btnfg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--btn); }
button:disabled { opacity: .45; cursor: default; }
.legend { display: flex; flex-wrap: wrap; gap: .3rem .8rem; margin-top: .6rem; font-size: .78rem; color: var(--muted); }
.legend span { display: inline-flex; align-items: center; gap: .3rem; }
.sw { display: inline-block; width: 22px; height: 0; border-top: 3px solid; }
.sw.tree { border-color: var(--tree); } .sw.back { border-color: var(--back); border-top-style: dashed; }
.sw.forward { border-color: var(--forward); border-top-style: dotted; } .sw.cross { border-color: var(--cross); border-top-style: dashed; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; border: 1.5px solid var(--nstroke); }
.dot.white { background: var(--nwhite); } .dot.grey { background: var(--ngrey); } .dot.black { background: var(--nblack); }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Three small graphs. Neighbours are visited in alphabetical order so every run is reproducible.
const PRESETS = {
  dag: { undirected: false,
    nodes: { A: [40, 40], B: [130, 40], D: [220, 40], G: [310, 40], C: [40, 125], E: [130, 125], H: [220, 125], I: [310, 125], F: [130, 205] },
    edges: ['AB', 'AC', 'AE', 'BD', 'BE', 'DG', 'EG', 'EH', 'CE', 'CF', 'FH', 'HI', 'GI'] },
  cycle: { undirected: false,
    nodes: { A: [40, 40], B: [130, 40], D: [220, 40], G: [310, 40], C: [40, 125], E: [130, 125], H: [220, 125], I: [310, 125], F: [130, 205] },
    edges: ['AB', 'AC', 'AE', 'BD', 'BE', 'DG', 'EG', 'EH', 'CE', 'CF', 'FH', 'HI', 'GI', 'HB'] },
  maze: { undirected: true,
    nodes: { A: [60, 40], B: [175, 40], C: [290, 40], D: [60, 125], E: [175, 125], F: [290, 125], G: [60, 205], H: [175, 205], I: [290, 205] },
    edges: ['AB', 'AD', 'BC', 'CF', 'DG', 'GH', 'HI', 'HE', 'EB'] }
};

// Iterative DFS with an explicit stack of frames (node, next-neighbour index). Each call to step() does exactly one thing: start a tree, inspect one edge, or finish one node.
function makeDFS(G) {
  const names = Object.keys(G.nodes).sort();
  const adj = {};
  names.forEach(n => { adj[n] = []; });
  G.edges.forEach((e, id) => {
    adj[e[0]].push({ v: e[1], id });
    if (G.undirected) adj[e[1]].push({ v: e[0], id });
  });
  names.forEach(n => adj[n].sort((a, b) => (a.v < b.v ? -1 : a.v > b.v ? 1 : a.id - b.id)));
  const S = { names, adj, color: {}, d: {}, f: {}, kind: {}, stack: [], time: 0, finished: [], backEdges: [], done: false, cur: null };
  names.forEach(n => { S.color[n] = 'white'; });
  // A frame remembers which neighbour to try next, so we never push the same node twice.
  function discover(u, pe) { S.d[u] = ++S.time; S.color[u] = 'grey'; S.stack.push({ u, i: 0, pe }); }
  S.step = function () {
    S.cur = null;
    if (S.done) return { type: 'done' };
    if (!S.stack.length) {
      const r = names.find(n => S.color[n] === 'white');
      if (r === undefined) { S.done = true; return { type: 'done' }; }
      discover(r, -1);
      return { type: 'start', u: r, d: S.d[r] };
    }
    const fr = S.stack[S.stack.length - 1];
    const u = fr.u;
    if (fr.i < adj[u].length) {
      const { v, id } = adj[u][fr.i++];
      S.cur = id;
      // Undirected graphs: the edge back to the parent and edges already seen from the other end are not new edges.
      if (G.undirected && id === fr.pe) return { type: 'parent', u, v, id };
      if (G.undirected && S.kind[id]) return { type: 'seen', u, v, id };
      // White = tree edge, grey = back edge (cycle), black = forward if v was discovered after u, otherwise cross.
      const c = S.color[v];
      if (c === 'white') { S.kind[id] = 'tree'; discover(v, id); return { type: 'tree', u, v, id, d: S.d[v] }; }
      if (c === 'grey') { S.kind[id] = 'back'; S.backEdges.push(id); return { type: 'back', u, v, id }; }
      const k = S.d[u] < S.d[v] ? 'forward' : 'cross';
      S.kind[id] = k;
      return { type: k, u, v, id };
    }
    // No neighbours left: assign the finish time, colour the node black and pop it (backtrack).
    S.stack.pop();
    S.f[u] = ++S.time;
    S.color[u] = 'black';
    S.finished.push(u);
    return { type: 'finish', u, f: S.f[u] };
  };
  return S;
}

const NS = 'http://www.w3.org/2000/svg';
const R = 15;
const svg = document.getElementById('g');
const presetSel = document.getElementById('preset');
const statusEl = document.getElementById('status');
const resultEl = document.getElementById('result');
const runBtn = document.getElementById('run');
const stepBtn = document.getElementById('step');
let G = PRESETS.dag, S = null, timer = null;

function el(tag, attrs, parent) {
  const e = document.createElementNS(NS, tag);
  for (const k in attrs) e.setAttribute(k, attrs[k]);
  if (parent) parent.appendChild(e);
  return e;
}
const sep = () => (G.undirected ? '–' : '→');
const edgeText = (id) => G.edges[id][0] + sep() + G.edges[id][1];

// Draw edges, then nodes with their discovery/finish stamps, then the stack.
function render() {
  svg.innerHTML = '';
  const defs = el('defs', {}, svg);
  ['unseen', 'tree', 'back', 'forward', 'cross'].forEach(k => {
    const m = el('marker', { id: 'm-' + k, viewBox: '0 0 10 10', refX: '9', refY: '5', markerWidth: '6', markerHeight: '6', orient: 'auto-start-reverse' }, defs);
    el('path', { d: 'M0,0 L10,5 L0,10 z', class: 'mk-' + k }, m);
  });
  const top = S.stack.length ? S.stack[S.stack.length - 1].u : null;
  G.edges.forEach((e, id) => {
    const [x1, y1] = G.nodes[e[0]], [x2, y2] = G.nodes[e[1]];
    const len = Math.hypot(x2 - x1, y2 - y1), ux = (x2 - x1) / len, uy = (y2 - y1) / len;
    // Trim each line so it stops at the circle border (and leaves room for the arrowhead).
    const pad = G.undirected ? R : R + 2;
    const k = S.kind[id] || 'unseen';
    const attrs = { x1: x1 + ux * R, y1: y1 + uy * R, x2: x2 - ux * pad, y2: y2 - uy * pad,
      class: 'edge ' + k + (S.cur === id ? ' cur' : '') };
    if (!G.undirected) attrs['marker-end'] = 'url(#m-' + k + ')';
    el('line', attrs, svg);
  });
  S.names.forEach(n => {
    const [x, y] = G.nodes[n];
    const g = el('g', { class: 'node ' + S.color[n] + (n === top ? ' top' : '') }, svg);
    el('circle', { cx: x, cy: y, r: R }, g);
    el('text', { x, y, class: 'nm' }, g).textContent = n;
    if (S.d[n]) el('text', { x, y: y + R + 13, class: 'tm' }, g).textContent = S.d[n] + '/' + (S.f[n] || '·');
  });
  const st = document.getElementById('stack');
  st.innerHTML = '';
  if (!S.stack.length) {
    const c = document.createElement('span'); c.className = 'chip none'; c.textContent = "empty"; st.appendChild(c);
  }
  S.stack.forEach((fr, i) => {
    const c = document.createElement('span');
    c.className = 'chip' + (i === S.stack.length - 1 ? ' top' : '');
    c.textContent = fr.u; st.appendChild(c);
  });
  document.getElementById('clock').textContent = i18nFmt("time = %t%", { t: S.time });
}

function say(text, cls) { statusEl.textContent = text; statusEl.className = 'status ' + (cls || ''); }

function describe(ev) {
  const e = ev.id !== undefined ? edgeText(ev.id) : '';
  const p = { e, u: ev.u, v: ev.v, d: ev.d, f: ev.f };
  switch (ev.type) {
    case 'start': return [i18nFmt("The stack is empty — start a new DFS tree at %u% (d = %d%).", p), ''];
    case 'tree': return [i18nFmt("%e%: %v% is white → tree edge. Go deeper (d = %d%).", p), ''];
    case 'back': return [i18nFmt("%e%: %v% is grey, still on the stack → back edge. Cycle found!", p), 'bad'];
    case 'forward': return [i18nFmt("%e%: %v% is black and a descendant of %u% → forward edge.", p), ''];
    case 'cross': return [i18nFmt("%e%: %v% is black in a branch that already finished → cross edge.", p), ''];
    case 'parent': return [i18nFmt("%e%: the corridor we just came through — skip it.", p), ''];
    case 'seen': return [i18nFmt("%e%: already classified from the other end — skip it.", p), ''];
    case 'finish': return [i18nFmt("%u% has no unexplored edges → finish it (f = %f%) and backtrack.", p), ''];
  }
  return ['', ''];
}

function showResult() {
  if (S.done) {
    if (G.undirected) {
      resultEl.textContent = i18nFmt("Every cell reached. The blue tree edges form a spanning tree of the maze; back edges closing a loop: %n%.", { n: S.backEdges.length });
      resultEl.className = 'result ok';
    } else if (S.backEdges.length) {
      resultEl.textContent = i18nFmt("Back edge %e% closes a cycle, so no topological order exists.", { e: edgeText(S.backEdges[0]) });
      resultEl.className = 'result bad';
    } else {
      resultEl.textContent = i18nFmt("No back edge, so this is a DAG. Topological order (reverse finish times): %order%", { order: S.finished.slice().reverse().join(' ') });
      resultEl.className = 'result ok';
    }
  } else if (S.backEdges.length) {
    resultEl.textContent = G.undirected ? "⟲ Loop found (a back edge)" : "⟲ Cycle found (a back edge)";
    resultEl.className = 'result bad';
  } else {
    resultEl.textContent = '';
    resultEl.className = 'result';
  }
}

function step() {
  const ev = S.step();
  if (ev.type === 'done') { stop(); say("Search complete: every node is black.", 'ok'); stepBtn.disabled = true; runBtn.disabled = true; }
  else { const [t, c] = describe(ev); say(t, c); }
  render();
  showResult();
}

function stop() { if (timer) { clearInterval(timer); timer = null; } runBtn.textContent = "Run"; }

// Run calls step() on a timer until the search is done.
function toggleRun() {
  if (timer) { stop(); return; }
  runBtn.textContent = "Pause";
  timer = setInterval(step, 650);
  step();
}

function reset() {
  stop();
  G = PRESETS[presetSel.value] || PRESETS.dag;
  S = makeDFS(G);
  stepBtn.disabled = false; runBtn.disabled = false;
  say("Press Step to begin at node A, or Run to animate.", '');
  render();
  showResult();
}

stepBtn.addEventListener('click', () => { stop(); step(); });
runBtn.addEventListener('click', toggleRun);
document.getElementById('reset').addEventListener('click', reset);
presetSel.addEventListener('change', reset);
reset();

Result

Console

Things to watch for:

The stack is the current path. Every grey node is on it; the moment a node turns black it is popped and the search backtracks to its parent.
The d/f stamps under the nodes never interleave: for any two nodes, their intervals are either nested or disjoint. That is the parenthesis theorem in action.
In the acyclic preset you will see forward (green) and cross (orange) edges but no back edge — and at the end the demo reads off a topological order by sorting nodes by decreasing finish time.
Switch to With a cycle: the single extra edge H→B reaches a grey node, the search reports a back edge, and no topological order can exist.
The maze is undirected: there, every edge is either a tree edge or a back edge, and the blue tree edges form a spanning tree of the maze.

The Real Complexity

Time. With adjacency lists, DFS visits every vertex once and examines every edge once (twice in an undirected graph, once from each end), so it runs in $\Theta(V + E)$ — linear in the size of the graph. There is no best or worst case to speak of: a full traversal always costs exactly that. With an adjacency matrix the cost becomes $\Theta(V^{2})$ , because finding the neighbours of a vertex means scanning a whole row.

Space. Colours and timestamps take $O(V)$ ; the stack holds at most one entry per grey vertex, so it is also $O(V)$ . That bound is tight: on a long path the stack reaches depth $V$ . With recursion this is a real-world hazard — a chain of a few hundred thousand nodes overflows the call stack of most languages. The fix is an iterative DFS that keeps an explicit stack of frames (vertex, index of next neighbour). Beware the tempting shortcut "pop a node, push all its neighbours": it visits nodes in a depth-first-like order, but the stack can grow to $O(E)$ and the discovery/finish times no longer have the properties below. (The demo above uses the frame-based version.)

The timestamp structure. DFS uses $2V$ ticks of the clock, and the times encode the search tree:

Parenthesis theorem. For any vertices $u, v$ , the intervals $[d_u, f_u]$ and $[d_v, f_v]$ are either disjoint or one contains the other. Write "(" at each discovery and ")" at each finish and you get a well-formed parenthesisation.
White-path theorem. $v$ becomes a descendant of $u$ if and only if, at time $d_u$ , there is a path from $u$ to $v$ made entirely of white vertices.

Edge classification (directed graph). When the search inspects edge $(u, v)$ , the colour of $v$ decides its type:

Tree edge — $v$ is white: the search goes deeper.
Back edge — $v$ is grey, i.e. an ancestor still on the stack: $d_v \le d_u < f_u \le f_v$ .
Forward edge — $v$ is black and a descendant of $u$ : $d_u < d_v < f_v < f_u$ .
Cross edge — $v$ is black in an already-finished subtree: $d_v < f_v < d_u < f_u$ .

In an undirected graph only tree and back edges can occur.

A back edge exists if and only if the graph has a cycle. One direction is immediate (a back edge plus the tree path from $v$ down to $u$ is a cycle). For the other, let $v$ be the first vertex of a cycle to be discovered: by the white-path theorem the rest of the cycle becomes its descendants, and the cycle edge that returns to $v$ is a back edge. So cycle detection is $O(V + E)$ .

Topological sort for free. If there is no back edge, every edge $(u, v)$ satisfies $f_v < f_u$ . Listing vertices by decreasing finish time is therefore a valid topological order — again in linear time.

The real payoff came from Tarjan's 1972 paper Depth-First Search and Linear Graph Algorithms: by tracking for each vertex the lowest discovery time reachable through its subtree plus one back edge (the "low-link"), a single DFS finds all strongly connected components and all bridges and articulation points. Hopcroft and Tarjan's 1974 planarity test pushed the same idea to decide in linear time whether a graph can be drawn without crossings. Hopcroft and Tarjan received the 1986 Turing Award "for fundamental achievements in the design and analysis of algorithms and data structures" — work in which DFS played a central role.

Where It Matters

Depth-first search is less a single algorithm than a skeleton that many others are built on:

Build systems and package managers. Make, Bazel, npm and friends model tasks and packages as a dependency graph. A DFS finds circular dependencies (a back edge) and produces the order in which things must be built — reverse finish order, i.e. a topological sort.
Strongly connected components. Tarjan's algorithm (one DFS with low-links) and Kosaraju's (two DFS passes, the second on the reversed graph) split a directed graph into strongly connected components — used in compilers, model checkers and 2-SAT solvers.
Network reliability. The same low-link trick in an undirected graph finds bridges and articulation points: the single links or routers whose failure disconnects the network.
Mazes. The recursive backtracker, one of the most popular maze generation algorithms, is literally a randomised DFS over a grid: carve into a random unvisited neighbour, backtrack at dead ends. It produces long, winding corridors — exactly the shape of a DFS tree.
Backtracking search. Solving a Sudoku, placing N queens on a chessboard or running the DPLL procedure for SAT are all DFS over a tree of partial solutions: extend the current choice, and backtrack as soon as a constraint is violated. Iterative deepening (Korf, 1985) runs depth-limited DFS with limits 1, 2, 3, …, getting the small memory of DFS together with the shortest-solution guarantee of breadth-first search.
Garbage collection. The mark phase of a tracing collector is a graph traversal from the roots; many implementations use an explicit mark stack, i.e. DFS, to flag every reachable object.

Whenever an algorithm needs to "follow a thread to its end, then come back", DFS is usually underneath.

Conclusion

Depth-first search starts as common sense — go as far as you can, then step back — and ends as one of the sharpest tools in algorithm design. Its cost is the minimum imaginable, $O(V + E)$ , yet the two timestamps it leaves on every vertex reveal cycles, dependency orders, tightly knit components and fragile links.

Remember the trade-offs: DFS does not find shortest paths (that is breadth-first search's job on unweighted graphs), and a naively recursive version can overflow the stack on deep graphs. But when you need to understand the structure of a graph rather than distances in it, Trémaux's chalk and Tarjan's timestamps are still the place to start.

Comments

Loading comments...

https://www.kipuhub.com/en/article/depth-first-search/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Depth-First Search (DFS)

The maze walker's rule that became a toolbox of linear-time algorithms