Depth-first search

coreCommon atGoogleMetaAmazonAnthropicRead firstRecursionGraph representationStacksPractise in the Sandbox →

Depth-first search (DFS) commits to one neighbour, explores everything reachable from it, and only then backtracks to try the next. A stack (the call stack, or your own) remembers the path back. It visits every reachable node once in O(V + E), and the order it enters and leaves nodes (pre- and post-order) answers questions about cycles, ordering and structure.

The idea in plain words

You’re in a maze with a ball of string. At every junction you take the first unexplored corridor and keep going. At a dead end you follow the string back to the last junction with an unexplored corridor. You never walk a corridor twice in the same direction.

That’s DFS. The string is the stack: the chain of nodes from the start to where you are now. Two facts make it useful:

• It visits everything reachable, each node once, as long as you mark nodes as visited when you enter them.
• It has a notion of “inside”. When DFS finishes a node, every node reachable from it that wasn’t already visited has been finished first. That nesting is what pre-order, post-order, cycle detection and topological sort all rely on.

DFS does not find shortest paths. The first route it finds to a node is just the first one it stumbled into. For fewest steps, use BFS.

See it

Flood fill. Click to add walls or move S, then step. Numbers are the visit order. In recursive mode the right panel is the call stack; each frame remembers which direction to try next. Switch to iterative to see the explicit-stack version, including the stale entries it has to skip.

DFS flood fill: go deep, then back up

click to edit, then step

RoomsSpiralOpenClear walls

0

call stack (top first), 1

fill(2,2)

visited1

depth1

max depth1

current callon the call stack (gray)finished (black)

Call fill(2,2). Mark it visited (#0) before looking at neighbours, so no path can loop back into it.

↺◀▶ Play▶1 / 99

Try the Spiral preset: the call stack gets as deep as the corridor is long. On a 1000×1000 open grid, recursive DFS can need a million frames, far past Python’s default limit of 1000.

Colours and edge types. On a directed graph, DFS paints nodes white (unseen), gray (on the current path) and black (finished), and stamps each node with a discover/finish time. Each edge it examines falls into one of four kinds. Edit the edges and watch for back edges: they are exactly the cycles.

Gray, black and the four edge types

step through

directed edges (a>b, …), up to 9 nodes

stack (gray path)

(empty)

pre-order (discover)

(empty)

post-order (finish)

(empty)

time0

back edges0

gray: on the stackblack: finished / tree edge (t)back edge (b): cycleforward edge (f)cross edge (c)

Badges under nodes are discover/finish times.

Every node starts white (unseen). Gray means "on the current path, still being explored". Black means "finished".

↺◀▶ Play▶1 / 26

When to reach for it

The problem says…	Why DFS fits
“is there a path”, “can you reach”, “connected?”	Any traversal works; DFS is the shortest to write.
“count / size of regions, islands, components”	Start a DFS from every unvisited cell; each start is a new region.
“flood fill”, “paint bucket”, “capture surrounded regions”	Fill everything reachable from a seed.
“detect a cycle” in a directed graph, “deadlock”, “circular dependency”	A back edge to a gray node is a cycle.
“order tasks so dependencies come first”	Reverse post-order is a topological order.
“all paths”, “all combinations”	DFS over choices is backtracking.
tree problems: height, subtree sums, validate a BST	A tree DFS is plain recursion; compute on the way back up (post-order).

How it works

1. Enter u: mark it visited (gray) and do any pre-order work.
2. For each neighbour v of u: if v is unvisited, recurse into it. Otherwise skip it (or classify the edge).
3. Leave u: all its unvisited descendants are done. Mark it finished (black) and do any post-order work.
4. To cover a whole graph, loop over all nodes and start a DFS from each one still unvisited.

Python

pre-order and post-order.py

Graph = dict[str, list[str]]


def orders_recursive(adj: Graph, start: str) -> tuple[list[str], list[str]]:
    """Pre-order (on entry) and post-order (on exit) of a DFS from start."""
    seen: set[str] = set()
    pre: list[str] = []
    post: list[str] = []

    def visit(u: str) -> None:
        seen.add(u)                 # 1. mark on entry, so cycles can't re-enter u
        pre.append(u)
        for v in adj.get(u, []):
            if v not in seen:       # 2. go deep into the first unseen neighbour
                visit(v)
        post.append(u)              # 3. all of u's descendants are done

    visit(start)
    return pre, post


def preorder_iterative(adj: Graph, start: str) -> list[str]:
    """Same pre-order with an explicit stack: no recursion-depth limit."""
    seen: set[str] = set()
    pre: list[str] = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:               # stale entry pushed by an earlier neighbour
            continue
        seen.add(u)
        pre.append(u)
        for v in reversed(adj.get(u, [])):  # reversed so the first neighbour is popped first
            if v not in seen:
                stack.append(v)
    return pre


if __name__ == "__main__":
    g = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"]}  # has a cycle back to a
    pre, post = orders_recursive(g, "a")
    assert pre == ["a", "b", "d", "c"]
    assert post == ["d", "b", "c", "a"]
    assert preorder_iterative(g, "a") == pre
    print("ok")

TypeScript

pre-order and post-order.ts

import assert from "node:assert/strict";

type Graph = Map<string, string[]>;

/** Pre-order (on entry) and post-order (on exit) of a DFS from start. */
export function ordersRecursive(adj: Graph, start: string) {
  const seen = new Set<string>();
  const pre: string[] = [];
  const post: string[] = [];
  const visit = (u: string): void => {
    seen.add(u); // 1. mark on entry, so cycles can't re-enter u
    pre.push(u);
    for (const v of adj.get(u) ?? []) {
      if (!seen.has(v)) visit(v); // 2. go deep into the first unseen neighbour
    }
    post.push(u); // 3. all of u's descendants are done
  };
  visit(start);
  return { pre, post };
}

/** Same pre-order with an explicit stack: no recursion-depth limit. */
export function preorderIterative(adj: Graph, start: string): string[] {
  const seen = new Set<string>();
  const pre: string[] = [];
  const stack = [start];
  while (stack.length > 0) {
    const u = stack.pop()!;
    if (seen.has(u)) continue; // stale entry pushed by an earlier neighbour
    seen.add(u);
    pre.push(u);
    const next = adj.get(u) ?? [];
    for (let i = next.length - 1; i >= 0; i--) { // reversed so the first neighbour is popped first
      if (!seen.has(next[i])) stack.push(next[i]);
    }
  }
  return pre;
}

const g: Graph = new Map(Object.entries({ a: ["b", "c"], b: ["d"], c: ["d"], d: ["a"] })); // cycle back to a
const { pre, post } = ordersRecursive(g, "a");
assert.deepEqual(pre, ["a", "b", "d", "c"]);
assert.deepEqual(post, ["d", "b", "c", "a"]);
assert.deepEqual(preorderIterative(g, "a"), pre);
console.log("ok");

C#

pre-order and post-order.cs

var g = new Dictionary<string, List<string>>
{
    ["a"] = ["b", "c"], ["b"] = ["d"], ["c"] = ["d"], ["d"] = ["a"], // cycle back to a
};
var (pre, post) = OrdersRecursive(g, "a");
if (string.Join("", pre) != "abdc") throw new Exception("pre-order");
if (string.Join("", post) != "dbca") throw new Exception("post-order");
if (string.Join("", PreorderIterative(g, "a")) != "abdc") throw new Exception("iterative");
Console.WriteLine("ok");

// Pre-order (on entry) and post-order (on exit) of a DFS from start.
static (List<string>, List<string>) OrdersRecursive(Dictionary<string, List<string>> adj, string start)
{
    var seen = new HashSet<string>();
    List<string> pre = [], post = [];
    void Visit(string u)
    {
        seen.Add(u);                                    // 1. mark on entry, so cycles can't re-enter u
        pre.Add(u);
        foreach (var v in adj.GetValueOrDefault(u, []))
            if (!seen.Contains(v)) Visit(v);            // 2. go deep into the first unseen neighbour
        post.Add(u);                                    // 3. all of u's descendants are done
    }
    Visit(start);
    return (pre, post);
}

// Same pre-order with an explicit stack: no recursion-depth limit.
static List<string> PreorderIterative(Dictionary<string, List<string>> adj, string start)
{
    var seen = new HashSet<string>();
    var pre = new List<string>();
    var stack = new Stack<string>([start]);
    while (stack.Count > 0)
    {
        var u = stack.Pop();
        if (!seen.Add(u)) continue;                     // stale entry pushed by an earlier neighbour
        pre.Add(u);
        var next = adj.GetValueOrDefault(u, []);
        for (int i = next.Count - 1; i >= 0; i--)       // reversed so the first neighbour pops first
            if (!seen.Contains(next[i])) stack.Push(next[i]);
    }
    return pre;
}

The iterative version pushes neighbours in reverse so the first neighbour is popped first, giving the same pre-order as the recursion. It marks on pop, so a node can sit in the stack several times; the if seen: continue line handles that. Getting a true post-order iteratively takes more care: push (node, next_neighbour_index) frames, which is what the recursive view above shows.

Cycle detection in a directed graph

Python

has_cycle (white / gray / black).py

WHITE, GRAY, BLACK = 0, 1, 2


def has_cycle(adj: dict[str, list[str]]) -> bool:
    """True if the DIRECTED graph has a cycle. Gray = on the current DFS path."""
    color = {u: WHITE for u in adj}

    def visit(u: str) -> bool:
        color[u] = GRAY                       # 1. entering u: it's on the path
        for v in adj.get(u, []):
            c = color.get(v, WHITE)
            if c == GRAY:                     # 2. back edge to an ancestor: cycle
                return True
            if c == WHITE and visit(v):
                return True
        color[u] = BLACK                      # 3. leaving u: fully explored, cycle-free below
        return False

    # 4. start from every white node; the graph may be disconnected
    return any(color.get(u, WHITE) == WHITE and visit(u) for u in list(adj))


if __name__ == "__main__":
    assert has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]})
    assert not has_cycle({"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []})  # diamond: no cycle
    assert has_cycle({"x": [], "a": ["a"]})                                    # self-loop
    assert not has_cycle({})
    print("ok")

TypeScript

has_cycle (white / gray / black).ts

import assert from "node:assert/strict";

const enum Color { White, Gray, Black }

/** True if the DIRECTED graph has a cycle. Gray = on the current DFS path. */
export function hasCycle(adj: Map<string, string[]>): boolean {
  const color = new Map<string, Color>();
  const visit = (u: string): boolean => {
    color.set(u, Color.Gray); // 1. entering u: it's on the path
    for (const v of adj.get(u) ?? []) {
      const c = color.get(v) ?? Color.White;
      if (c === Color.Gray) return true; // 2. back edge to an ancestor: cycle
      if (c === Color.White && visit(v)) return true;
    }
    color.set(u, Color.Black); // 3. leaving u: fully explored, cycle-free below
    return false;
  };
  // 4. start from every white node; the graph may be disconnected
  for (const u of adj.keys()) {
    if ((color.get(u) ?? Color.White) === Color.White && visit(u)) return true;
  }
  return false;
}

const G = (o: Record<string, string[]>) => new Map(Object.entries(o));
assert.equal(hasCycle(G({ a: ["b"], b: ["c"], c: ["a"] })), true);
assert.equal(hasCycle(G({ a: ["b", "c"], b: ["d"], c: ["d"], d: [] })), false); // diamond: no cycle
assert.equal(hasCycle(G({ x: [], a: ["a"] })), true); // self-loop
assert.equal(hasCycle(G({})), false);
console.log("ok");

C#

has_cycle (white / gray / black).cs

Dictionary<string, List<string>> G(params (string, string[])[] es) => es.ToDictionary(e => e.Item1, e => e.Item2.ToList());
if (!HasCycle(G(("a", ["b"]), ("b", ["c"]), ("c", ["a"])))) throw new Exception("triangle");
if (HasCycle(G(("a", ["b", "c"]), ("b", ["d"]), ("c", ["d"]), ("d", [])))) throw new Exception("diamond has no cycle");
if (!HasCycle(G(("x", []), ("a", ["a"])))) throw new Exception("self-loop");
if (HasCycle(G())) throw new Exception("empty");
Console.WriteLine("ok");

// True if the DIRECTED graph has a cycle. Gray = on the current DFS path.
static bool HasCycle(Dictionary<string, List<string>> adj)
{
    var color = new Dictionary<string, Color>();
    bool Visit(string u)
    {
        color[u] = Color.Gray;                                  // 1. entering u: it's on the path
        foreach (var v in adj.GetValueOrDefault(u, []))
        {
            var c = color.GetValueOrDefault(v, Color.White);
            if (c == Color.Gray) return true;                   // 2. back edge to an ancestor: cycle
            if (c == Color.White && Visit(v)) return true;
        }
        color[u] = Color.Black;                                 // 3. leaving u: fully explored
        return false;
    }
    // 4. start from every white node; the graph may be disconnected
    return adj.Keys.Any(u => color.GetValueOrDefault(u, Color.White) == Color.White && Visit(u));
}

enum Color { White, Gray, Black }

Two colours aren't enough for directed graphs

With only visited/unvisited, the diamond a→b, a→c, b→d, c→d looks like a cycle: d is already visited when you reach it from c. It isn’t one. Only an edge to a node still on the current path (gray) closes a cycle. For undirected graphs the rule is different: any visited neighbour other than the one you came from means a cycle.

The four edge types

Edge u → v when examined	Kind	Meaning
v is white	tree	DFS descends into v.
v is gray	back	v is an ancestor of u: a cycle. Also self-loops.
v is black, discovered after u	forward	v is a descendant already finished through another path.
v is black, discovered before u	cross	v is in a branch that finished earlier.

In an undirected graph only tree and back edges occur. Forward and cross edges need direction.

What it costs

	Time	Extra space
Adjacency list, V nodes, E edges	O(V + E)	O(V) for seen plus the stack
Grid R × C	O(R·C)	O(R·C) worst case (a long snake-shaped corridor)
Recursive version, stack depth		O(longest DFS path), up to V
Iterative, mark-on-pop	O(V + E)	O(E): stale duplicates can pile up on the stack

Recursion limits matter in practice. Python’s default limit is 1000 frames (sys.getrecursionlimit()), and raising it with sys.setrecursionlimit can still crash the interpreter on its C stack. Node’s default stack fits on the order of ten thousand simple frames. .NET threads get 1 MB of stack by default. If the depth can reach ~10⁴ or more, go iterative.

Variations you’ll meet

• Flood fill with a counter. Return the number of cells filled to get a region’s size.
• Connected components. Run DFS from each unvisited node and label everything it reaches with a component id.
• Topological sort. Record nodes in post-order and reverse it. See topological sort.
• Tarjan / Kosaraju for strongly connected components, and bridges / articulation points via discovery times and “low-link” values. Advanced, but built on the same discover/finish times.
• DFS on a tree with return values. Height, diameter, path sums: compute children first, combine on the way up.
• Iterative deepening (IDDFS). DFS with a depth cap that grows 1, 2, 3…: BFS’s shortest-path guarantee with DFS’s small memory.

Pitfalls

• Marking too late. Mark on entry. Marking after the loop lets a cycle re-enter the node forever.
• Two colours for directed cycles (see the caution above).
• Recursion depth on large grids or long chains.
• Forgetting disconnected parts. A single DFS from node 0 misses other components. Loop over all nodes.
• Expecting shortest paths. DFS paths are valid, not short.
• Undirected cycle check that forgets to ignore the parent edge: every edge then looks like a 2-cycle.

In the interview

• Ask: directed or undirected? Can it be disconnected? How big (recursion depth)? 4- or 8-neighbour grid? May I mutate the input?
• Say: “I’ll mark on entry, so each node is visited once: O(V + E).”
• Mention the recursion limit before you’re asked, and offer the iterative version.
• For cycles in a directed graph, name the three colours and explain why visited-only is wrong.
• Expected follow-ups: return the size of each region, find the cycle itself (keep a parent map and walk back from the back edge), make it iterative, or switch to BFS for distances.

Check yourself

Check yourself

pick one

In a directed graph, DFS from u finds that neighbour v is already visited and black. Does that mean there's a cycle?

AYes, any visited neighbour means a cycleBNo: a black node is finished and not on the current path, so the edge is forward or crossCOnly if v has a smaller discovery time

Check yourself

pick one

Recursive DFS over a 2000 × 2000 open grid crashes in Python. What's the most reliable fix?

Asys.setrecursionlimit(10**7)BSwitch to an explicit stack (or BFS) so depth no longer uses the call stackCVisit neighbours in a different orderDUse memoization

Check yourself

pick one

Which DFS order gives a valid dependency-first ordering of a DAG (every edge u→v puts u before v)?

APre-orderBPost-orderCReverse post-orderDDiscovery time order

Practice on your own

These are classic textbook exercises, not gym questions:

• Paint-bucket fill: recolour the region containing a clicked pixel.
• Capture every O region on a board that doesn’t touch the border.
• Count connected components of an undirected graph given as an edge list.
• Find all cells from which water can flow to both the top-left and bottom-right edges of a height map.
• Clone a graph given a reference to one node.

Go deeper

• CLRS, Introduction to Algorithms, “Elementary Graph Algorithms”: depth-first search, the parenthesis theorem, white-path theorem and edge classification.
• cp-algorithms: Depth-first search, including entry/exit times and edge types.
• Sedgewick and Wayne, Algorithms 4.2: Directed graphs, DirectedCycle and DepthFirstOrder.
• Python docs: sys.setrecursionlimit, on why raising the limit can still crash.

Related

Breadth-first searchWhen you need fewest steps, not just reachability.

Topological sortReverse post-order and Kahn's algorithm.

BacktrackingDFS over a tree of choices, with undo.

Union-findComponents without traversal, and online as edges arrive.