On this page

DFS in Depth

Why this exists

BFS answers "how far?". Depth-first search answers "what is the structure?". Does this dependency graph have a cycle? Which cells form this island? Is this undirected graph a tree? In what order must these tasks run? Which vertices are articulation points whose removal disconnects a network? Every one of those questions is answered by a single depth-first traversal plus a little bookkeeping, in time. DFS is the skeleton under topological sort, strongly connected components, bridges and articulation points (connectivity), Euler tours, planarity testing and almost every backtracking search.

The idea predates computers. In the 19th century the French engineer Charles Pierre Trémaux described a method for escaping any maze: walk until you hit a junction, mark the passage you came from, always prefer unmarked passages, and turn back only when every passage from here is marked. That is DFS executed with chalk, and it is guaranteed to explore the whole maze. The modern form, with discovery and finish times and the classification of edges, was developed by John Hopcroft and Robert Tarjan in the early 1970s; Tarjan's 1972 paper "Depth-first search and linear graph algorithms" used it to find strongly connected components and biconnected components in linear time, and Hopcroft and Tarjan's 1974 linear-time planarity test was a landmark built on the same tool. They received the 1986 Turing Award in part for this work.

The Graphs overview gave recursive and iterative DFS in a few lines and the three-colour cycle check. This lesson explains what DFS records — the timestamps — and the two theorems (parenthesis and white-path) that make those timestamps so powerful; classifies every edge; detects cycles in directed and undirected graphs and returns them; covers components and flood fill; analyses iterative deepening; uses DFS as a backtracking engine; and deals honestly with recursion depth in each language, including why the "obvious" iterative DFS visits vertices in a different order from the recursive one.

Pattern triggers

If the problem says or has…Think of…
"number of islands / regions / provinces / connected groups"DFS (or BFS) from every unvisited vertex; count the starts
"fill", "paint bucket", "capture regions surrounded by…"Flood fill on a grid
"is there a cycle?", "can all courses be finished?", "deadlock"Directed: three-colour DFS (back edge). Undirected: visited non-parent neighbour
"find / print a cycle"DFS with parent pointers; walk back from the back edge
"order the tasks so prerequisites come first"DFS finish order reversed = topological order
"is this graph a tree?"Connected and , or DFS with no back edge reaching every vertex
"all paths from s to t", "every arrangement", "visit each cell exactly once"DFS as backtracking (exponential; check is small)
"which nodes are always safe / eventually terminate"Three-colour DFS on the graph, or reverse graph + Kahn
"bridges", "critical connections", "articulation points", "strongly connected"DFS with discovery times and low-links (connectivity)
Search tree with unknown solution depth and too little memory for BFSIterative deepening DFS
Recursion depth may reach – (long chains, big grids)Iterative DFS with an explicit stack of iterators
"is u an ancestor of v?" many times on a treeDFS entry/exit times: is an ancestor iff its interval contains 's

The meta-trigger: the answer depends on how the graph is connected — reachability, cycles, nesting, ordering — not on shortest distances. If the problem asks for the fewest steps, you want BFS instead.

Intuition & first principles

Explore a cave with a ball of thread. At each junction take an unexplored passage; when you reach a dead end or a junction you have already seen, wind the thread back to the last junction that still has an unexplored passage. The thread is the recursion stack: it is exactly the path from the entrance to where you stand. You never get lost, you never walk an unexplored passage twice, and you explore everything reachable.

Two moments in each vertex's life matter. The discovery time is when you first arrive (the thread is extended to ). The finish time is when you leave for good, having explored everything reachable from it that was still unexplored (the thread is wound back past ). Between and , is on the thread — "gray" in the classic colouring; before, it is "white" (undiscovered); after, "black" (finished).

flowchart LR
    W["WHITE: not yet discovered"] -->|"discover: d[v] = ++time"| G["GRAY: on the stack"]
    G -->|"all edges explored: f[v] = ++time"| B["BLACK: finished"]

Why does this bookkeeping matter? Because the stack structure forces the intervals to nest like parentheses: if you enter while is on the thread, you must leave before you can leave . Nesting means intervals encode the DFS forest exactly — is an ancestor of iff 's interval contains 's. And the colour of a vertex at the moment you look at an edge to it tells you what kind of edge it is: an edge to a gray vertex points back up the thread, which means a cycle. That one observation is the cycle detector, the topological sorter and the start of the strongly-connected-components algorithms.

Mechanics

Recursive DFS with times

DFS(G):
    for each vertex u: colour[u] = WHITE
    time = 0
    for each vertex u:
        if colour[u] == WHITE: VISIT(u)       # u becomes the root of a new DFS tree

VISIT(u):
    time += 1; d[u] = time; colour[u] = GRAY
    for each v in adj[u]:
        if colour[v] == WHITE:               # tree edge
            parent[v] = u
            VISIT(v)
        # otherwise classify (u, v): GRAY -> back, BLACK and d[u] < d[v] -> forward, else cross
    time += 1; f[u] = time; colour[u] = BLACK

Each vertex gets exactly two timestamps, so times run from 1 to . The parent edges form the DFS forest: one tree per call from the outer loop.

The example graph

Eight vertices, thirteen directed edges, adjacency in the order shown (A: B, E, C; B: D, E; C: F; D: A; E: D; F: C, E; G: F, H; H: G). The labels show the edge classes that the DFS below assigns.

flowchart LR
    A["A 1/12"] -->|"tree"| B["B 2/7"]
    B -->|"tree"| D["D 3/4"]
    D -->|"back"| A
    B -->|"tree"| E["E 5/6"]
    E -->|"cross"| D
    A -->|"forward"| E
    A -->|"tree"| C["C 8/11"]
    C -->|"tree"| F["F 9/10"]
    F -->|"back"| C
    F -->|"cross"| E
    G["G 13/16"] -->|"cross"| F
    G -->|"tree"| H["H 14/15"]
    H -->|"back"| G

Trace: DFS from A, then G

Produced by running scripts/traces/dfs_graph.py (the same run the visualizer plays back). "Stack" is the recursion stack after the event; labels are d/f.

StepEventStack afterTimeLabels changedEdge class
1discover A[A]1A 1/–
2scan A→B[A]1tree (B white)
3discover B[A, B]2B 2/–
4scan B→D[A, B]2tree
5discover D[A, B, D]3D 3/–
6scan D→A[A, B, D]3back (A gray)
7finish D[A, B]4D 3/4
8scan B→E[A, B]4tree
9discover E[A, B, E]5E 5/–
10scan E→D[A, B, E]5cross (D black, d=3 < 5)
11finish E[A, B]6E 5/6
12finish B[A]7B 2/7
13scan A→E[A]7forward (E black, d[A]=1 < d[E]=5)
14scan A→C[A]7tree
15discover C[A, C]8C 8/–
16scan C→F[A, C]8tree
17discover F[A, C, F]9F 9/–
18scan F→C[A, C, F]9back (C gray)
19scan F→E[A, C, F]9cross (d[E]=5 < 9)
20finish F[A, C]10F 9/10
21finish C[A]11C 8/11
22finish A[]12A 1/12
23discover G (new root)[G]13G 13/–
24scan G→F[G]13cross (into the first tree)
25scan G→H[G]13tree
26discover H[G, H]14H 14/–
27scan H→G[G, H]14back
28finish H[G]15H 14/15
29finish G[]16G 13/16

Totals: 6 tree, 3 back, 1 forward, 3 cross — 13 edges. Two DFS trees, rooted at A and G. Three back edges, three cycles (A→B→D→A, C→F→C, G→H→G). Notice that every cross edge points from a later-discovered vertex to an earlier, already finished one (E→D, F→E, G→F); that is a theorem, not a coincidence, and it is why the reversed finish order is a topological order when there are no back edges.

The parenthesis structure

Write (v at and v) at , in time order: (A (B (D D) (E E) B) (C (F F) C) A) (G (H H) G). A well-formed parenthesization: that is the parenthesis theorem made visible. The DFS forest is the nesting:

flowchart TD
    A["A [1,12]"] --> B["B [2,7]"]
    A --> C["C [8,11]"]
    B --> D["D [3,4]"]
    B --> E["E [5,6]"]
    C --> F["F [9,10]"]
    G["G [13,16]"] --> H["H [14,15]"]

Parenthesis theorem (CLRS §20.3). For any two vertices and , exactly one holds: the intervals and are disjoint, and neither is a descendant of the other in the DFS forest; or is contained in and is a descendant of ; or the reverse.

White-path theorem. is a descendant of in the DFS forest if and only if, at time , there is a path from to consisting entirely of white vertices.

Practical consequences: the ancestor test "is an ancestor of ?" is the check and (used with Euler tours for LCA queries); and anything reachable from through undiscovered territory ends up inside 's subtree, which is what makes low-link algorithms work.

Edge classification

In a directed graph, an edge scanned from is:

ClassColour of when scannedTimesMeaning
Treewhite is discovered through this edge
Backgray is an ancestor of (self-loops count as back edges)
Forwardblack, is a descendant of , but not via this edge
Crossblack, neither is an ancestor of the other; finished earlier

In an undirected graph, every edge is a tree edge or a back edge — forward and cross edges cannot occur (proof below). The catch in code: when scans the edge back to its own parent, the parent is gray and the edge looks like a back edge. Skip the edge you arrived by (by vertex if the graph is simple, by edge id if it can have parallel edges).

Cycle detection, both ways

Directed: a directed graph has a cycle if and only if DFS finds a back edge. Run three-colour DFS from every white vertex; the moment an edge reaches a gray vertex, you have a cycle, and the cycle is that vertex followed by the stack from it down to . A two-colour version (visited / not) is wrong for directed graphs: in the example, E→D reaches an already-visited vertex but there is no cycle through it — it is a cross edge.

Undirected: a graph has a cycle if and only if DFS finds an edge to a visited vertex other than the parent it came from. Equivalently, a connected undirected graph is acyclic iff . Union-find is the alternative for streaming edges: an edge whose endpoints are already in the same set closes a cycle (union-find).

Connected components and flood fill

For undirected graphs, each call from the outer loop of DFS discovers exactly one connected component (by the white-path theorem, everything reachable from the root is white at that moment, so all of it lands in the root's tree). Counting the outer calls counts components; writing the call number into comp[v] labels them. On a grid this is flood fill: the paint-bucket tool, counting islands, finding enclosed regions. Directed graphs need more: "reachable from" is not symmetric, and the components that matter are strongly connected components (connectivity).

Iterative DFS, and why the naive version visits in a different order

Recursion has a depth limit (see the recursion section). The usual "fix" is to replace the call stack with an explicit stack — and the obvious way to do that changes the algorithm.

Take A: [B, C], B: [C, D]. Recursive DFS from A visits A, B, C, D: from B it takes C first (B's first neighbour), then D.

  1. Naive: push all neighbours, mark on pop. Pop A, push B then C. Pop C (last pushed). The order is A, C, B, D — neighbours are explored in reverse. Easy to fix by pushing in reverse order.
  2. Push all neighbours in reverse, mark on pop. Order A, B, C, D — the same preorder as recursion (I checked this against recursion on 20,000 random small digraphs: no differences). But a vertex can sit on the stack many times (once per incoming edge scanned), so the stack is , and there is no moment that corresponds to "finish", so no finish times, no gray/black distinction, no back-edge detection.
  3. Mark on push (the BFS habit). Pop A, mark and push C then B; pop B, mark and push D (C is already marked, so it is skipped); pop D; pop C. Order A, B, D, C. C is reached "from A" instead of "from B": a different DFS tree, and in fact not a depth-first tree at all — it violates the white-path theorem (when B was discovered, C was white and adjacent to B, so C should have become B's descendant).
  4. Faithful: a stack of (vertex, next-neighbour index) frames. Push (A, 0). Repeatedly look at the top frame; if it has a next neighbour, advance the index, and if that neighbour is white, discover it and push its frame; if the frame is exhausted, pop it and finish the vertex. This is exactly what the call stack does, so it produces identical discovery times, finish times and edge classes, with stack.

Use version 4 whenever you need finish times, edge classes, cycles, topological order or low-links. Versions 2 and 3 are fine when you only need the set of reachable vertices (components, flood fill), where order is irrelevant.

A stack of (vertex, next-neighbour) frames does exactly what the call stack does: same discovery order, same finish order, no recursion.

Iterative deepening DFS

BFS finds the shallowest goal but stores a whole layer, memory for branching factor and goal depth . DFS uses memory (the stack plus, per frame, the remaining siblings) but may dive forever down a wrong branch. Iterative deepening DFS (IDDFS, Korf 1985) gets both: run a depth-limited DFS with limit 0, then 1, then 2, …, until the goal is found. The first limit at which it succeeds is the goal's depth, so it is as shallow-optimal as BFS, and it never stores more than one path.

The repeated work is smaller than it looks, because in a tree with branching most nodes are in the last layer. Nodes at depth are generated once per iteration with limit , i.e. times:

BFS nodesIDDFS nodesOverhead
105111,111123,4561.11×
389,84114,7571.50×
2102,0474,0831.99×

The ratio tends to : 11% for , 2× for . Time stays ; memory drops from to . IDDFS beats BFS when the space is a huge tree (game trees, puzzle search with a heuristic as IDA*), when memory is the binding constraint, or when you have no visited set because states are too many to remember. It loses on graphs with many cycles or transpositions: without a visited set, it re-explores every path to a state, and the number of paths can be exponentially larger than the number of states (a grid has exponentially many paths between two cells). On such graphs, BFS with a visited set wins.

DFS as backtracking

When the question is "enumerate all simple paths", "is there a path visiting every vertex once", "count the tours", the visited set is no longer global — it is the set of vertices on the current path, added on entry and removed on exit. That turns DFS into backtracking, exploring every simple path rather than every vertex: exponential in general, which is unavoidable because the outputs themselves can be exponential.

  • All paths from source to target in a DAG (no cycles, so no on-path set is even needed): the number of paths can be in a DAG with vertices, and the DFS cost is proportional to the total output size.
  • All simple paths in a general graph: keep on_path; skip neighbours already on it.
  • Hamiltonian path check (preview): does some simple path visit all vertices? Backtracking with the on-path set answers it for up to about 10–12; the bitmask DP over (set visited, last vertex) handles in ; in general the problem is NP-complete. The full treatment is in Euler & Hamiltonian paths, and backtracking techniques (pruning, ordering) in backtracking & recursion.

Recursion depth, language by language

Recursive DFS on a path graph of vertices recurses deep. Typical limits, measured on our test machine (Windows 11, x64) with a trivial recursive function — real DFS frames are larger, so expect less:

LanguageDefault limitMeasuredHow to raise itNotes
Python (CPython 3.14)sys.getrecursionlimit() = 1000RecursionError at depth ≈ 1000sys.setrecursionlimit(n)On recent CPython, pure-Python recursion no longer consumes the C stack, and a depth of 500,000 ran fine after raising the limit; older versions could crash the interpreter, and the usual workaround was a threading.Thread with a larger threading.stack_size
Java 21thread stack size (-Xss, platform default often 512 KB–1 MB)≈ 21,000 frames on the main threadnew Thread(null, task, "dfs", 1L << 28) or -XssA 256 MB thread stack reached ≈ 15 million trivial frames
C++OS thread stack: commonly 8 MB on Linux (ulimit -s), 1 MB default on Windows (MSVC linker)not measured (depends on frame size and flags)ulimit -s unlimited on Linux, linker flags, or run in a thread with a set stack sizeOverflow is a segfault, not an exception
JavaScript (Node 24)V8 stack ≈ 1 MB≈ 10,400 framesnode --stack-size=...Raising --stack-size beyond the real OS thread stack crashes the process; our attempt with a very large value did

Rule of thumb: if the recursion depth can exceed about — a grid flood fill can recurse deep — write the iterative version from the start. The conversion is mechanical: each frame becomes (vertex, next index) (version 4 above), and any work done "after the recursive call returns" moves to where the child's frame is popped.

The ladder: brute force → better → optimal

Problem: does a directed graph with vertices and edges contain a cycle, and if so, print one?

Rung 1: from each vertex, search for a way back

For every vertex , run a traversal from and check whether is reachable from one of its own out-neighbours. Correct and simple. : with and that is , far too slow.

Rung 2: two-colour DFS (wrong)

One DFS, flag a cycle whenever an edge reaches an already visited vertex. , and wrong: cross and forward edges also reach visited vertices. On the example graph it would report a cycle at E→D, which closes none. This rung exists because it is the most common bug in interviews; on undirected graphs (with the parent edge excluded) the two-colour test is correct.

Rung 3: Kahn's algorithm

Repeatedly remove vertices of in-degree 0 (topological sort). If everything is removed, the graph is a DAG; otherwise the remaining vertices all lie on or lead to cycles. , iterative, no recursion. Extracting an actual cycle takes an extra walk among the remaining vertices (follow any remaining in-edge backwards until a vertex repeats).

Rung 4: three-colour DFS

One DFS; a back edge (to a gray vertex) proves a cycle, and the gray vertices on the stack from to are the cycle. , cycle extraction free, and the same traversal yields a topological order (reverse finish order) when there is no cycle.

RungMethodTimeSpaceCorrect?Why it improves
1Traversal from every vertexYesBaseline
2Two-colour DFSNo (directed)Fast, but confuses cross/forward edges with cycles
3Kahn (in-degree peeling)YesOne pass; no recursion
4Three-colour DFSYesOne pass; the stack is the cycle; also gives a topological order

Correctness

The proofs follow CLRS (4th ed., §20.3), compressed to sketches.

Parenthesis theorem

Suppose (otherwise swap names). Case 1: . Then was discovered while was gray, i.e. while VISIT(u) was on the call stack, so VISIT(v) was called (directly or indirectly) from within VISIT(u); it must return before VISIT(u) does, so , and is a descendant of (the chain of calls is the chain of parent edges). The intervals are nested. Case 2: . Then : disjoint intervals, and since was already black when was discovered, is not in 's subtree; nor is in 's (it was discovered earlier). Partial overlap () is impossible because it would violate Case 1's conclusion.

White-path theorem

() If is a descendant of , every vertex on the tree path from to is a descendant, so : at time all of them are white. () Suppose at time there is a white path , but does not become a descendant. Take the first on the path that does not become a descendant; does (or is ), so . is white at , so . And must be discovered before finishes, because VISIT(w_{i-1}) scans the edge to and would discover it if still white: . By the parenthesis theorem, lies inside , so is a descendant of . Contradiction.

A directed graph is acyclic iff DFS finds no back edge

(, contrapositive: a cycle forces a back edge.) Let be a cycle and its first vertex to be discovered; let be 's predecessor on . At the rest of is white, so by the white-path theorem becomes a descendant of . When VISIT(u) scans , is still gray (an ancestor that has not finished), so is a back edge. () A back edge means is an ancestor of , so the tree path plus is a cycle.

Every edge of an undirected DFS is a tree edge or a back edge

Take an edge with . Since is adjacent to and white at , the white-path theorem makes a descendant of , so finishes while is gray. If the edge is first explored from , is white at that moment (otherwise it would have been explored from first) — a tree edge. If it is first explored from , then is gray at that moment — a back edge. No other case exists, so there are no forward or cross edges. Corollary: an undirected graph is acyclic iff its DFS has no back edges other than the parent edge.

Cross edges point to earlier finishers

If is a cross edge, is black when scanned, so $f[v] < $ the current time . Combined with tree and forward edges ( too), every non-back edge goes from a later finisher to an earlier finisher — the reason "sort by decreasing finish time" is a topological order of a DAG.

Complexity

Time. Each vertex is discovered once (white → gray happens once) and finished once. Each adjacency list is scanned once, during the vertex's VISIT, so total scanning is (directed) or (undirected). Total with adjacency lists; with a matrix. Grid flood fill: .

Space. Colours, times and parents: . Stack depth: up to in the worst case (a path), in general. The faithful iterative version also uses frames; the "push all neighbours" version can use .

Best/average/worst. DFS for reachability or cycle detection can stop early (target found, first back edge), so best cases are small; worst case is . Backtracking DFS (all paths, Hamiltonian search) is exponential in the worst case, and that cost is in the problem, not the traversal.

IDDFS. Time with overhead factor about ; memory .

Constants and cache behaviour. Recursive DFS in Python costs a function call per vertex, which is several times slower than a loop; the iterative version is usually faster in Python and avoids the limit. In C++ and Java, recursive DFS is fast and the frames stay hot in cache, but the stack limit is real. Like BFS, DFS's cost on large graphs is dominated by random accesses to colour[v] for each scanned neighbour, so CSR layouts and vertex ordering matter more than the choice between recursion and a loop.

Implementation

DFS with times and edge classes, iteratively

A faithful iterative DFS (stack of (vertex, next index) frames) that records , and the class of every edge, run on the example graph (A..H = 0..7). The assertions check the exact values from the trace table, proving it matches the recursive run.

WHITE, GRAY, BLACK = 0, 1, 2


def dfs_classify(adj):
    n = len(adj)
    colour = [WHITE] * n
    d, f = [0] * n, [0] * n
    classes = {}
    time = 0
    for root in range(n):
        if colour[root] != WHITE:
            continue
        time += 1
        d[root] = time
        colour[root] = GRAY
        stack = [(root, 0)]
        while stack:
            u, i = stack[-1]
            if i < len(adj[u]):
                stack[-1] = (u, i + 1)          # advance this frame's iterator
                v = adj[u][i]
                if colour[v] == WHITE:
                    classes[(u, v)] = "tree"
                    time += 1
                    d[v] = time
                    colour[v] = GRAY
                    stack.append((v, 0))        # "recursive call"
                elif colour[v] == GRAY:
                    classes[(u, v)] = "back"
                elif d[u] < d[v]:
                    classes[(u, v)] = "forward"
                else:
                    classes[(u, v)] = "cross"
            else:
                stack.pop()                     # "return": finish u
                time += 1
                f[u] = time
                colour[u] = BLACK
    return d, f, classes


if __name__ == "__main__":
    A, B, C, D, E, F, G, H = range(8)
    adj = [[B, E, C], [D, E], [F], [A], [D], [C, E], [F, H], [G]]
    d, f, cls = dfs_classify(adj)
    assert d == [1, 2, 8, 3, 5, 9, 13, 14]
    assert f == [12, 7, 11, 4, 6, 10, 16, 15]
    assert cls[(D, A)] == cls[(F, C)] == cls[(H, G)] == "back"
    assert cls[(A, E)] == "forward"
    assert cls[(E, D)] == cls[(F, E)] == cls[(G, F)] == "cross"
    assert sum(c == "tree" for c in cls.values()) == 6 and len(cls) == 13
    # Parenthesis theorem: no two intervals partially overlap.
    for u in range(8):
        for v in range(8):
            assert not (d[u] < d[v] < f[u] < f[v])
    print("dfs classify OK")
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class DfsClassify {
    static final int WHITE = 0, GRAY = 1, BLACK = 2;
    static int[] d, f;
    static Map<Long, String> classes = new HashMap<>();

    static long key(int u, int v) { return (long) u * 1_000_003L + v; }

    static void run(int[][] adj) {
        int n = adj.length;
        int[] colour = new int[n];
        d = new int[n];
        f = new int[n];
        int time = 0;
        for (int root = 0; root < n; root++) {
            if (colour[root] != WHITE) continue;
            d[root] = ++time;
            colour[root] = GRAY;
            ArrayDeque<int[]> stack = new ArrayDeque<>();   // frames {vertex, next index}
            stack.push(new int[] {root, 0});
            while (!stack.isEmpty()) {
                int[] top = stack.peek();
                int u = top[0];
                if (top[1] < adj[u].length) {
                    int v = adj[u][top[1]++];
                    if (colour[v] == WHITE) {
                        classes.put(key(u, v), "tree");
                        d[v] = ++time;
                        colour[v] = GRAY;
                        stack.push(new int[] {v, 0});
                    } else if (colour[v] == GRAY) {
                        classes.put(key(u, v), "back");
                    } else if (d[u] < d[v]) {
                        classes.put(key(u, v), "forward");
                    } else {
                        classes.put(key(u, v), "cross");
                    }
                } else {
                    stack.pop();
                    f[u] = ++time;
                    colour[u] = BLACK;
                }
            }
        }
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        final int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7;
        int[][] adj = {{B, E, C}, {D, E}, {F}, {A}, {D}, {C, E}, {F, H}, {G}};
        run(adj);
        check(Arrays.equals(d, new int[] {1, 2, 8, 3, 5, 9, 13, 14}), "d");
        check(Arrays.equals(f, new int[] {12, 7, 11, 4, 6, 10, 16, 15}), "f");
        check(classes.get(key(D, A)).equals("back") && classes.get(key(F, C)).equals("back")
                && classes.get(key(H, G)).equals("back"), "back");
        check(classes.get(key(A, E)).equals("forward"), "forward");
        check(classes.get(key(E, D)).equals("cross") && classes.get(key(F, E)).equals("cross")
                && classes.get(key(G, F)).equals("cross"), "cross");
        long trees = classes.values().stream().filter(c -> c.equals("tree")).count();
        check(trees == 6 && classes.size() == 13, "counts");
        for (int u = 0; u < 8; u++)
            for (int v = 0; v < 8; v++)
                check(!(d[u] < d[v] && d[v] < f[u] && f[u] < f[v]), "parenthesis");
        System.out.println("dfs classify OK");
    }
}
#include <cassert>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>

enum Colour { WHITE, GRAY, BLACK };

struct Result {
    std::vector<int> d, f;
    std::map<std::pair<int, int>, std::string> classes;
};

Result dfsClassify(const std::vector<std::vector<int>>& adj) {
    int n = static_cast<int>(adj.size());
    std::vector<Colour> colour(n, WHITE);
    Result r{std::vector<int>(n, 0), std::vector<int>(n, 0), {}};
    int time = 0;
    for (int root = 0; root < n; ++root) {
        if (colour[root] != WHITE) continue;
        r.d[root] = ++time;
        colour[root] = GRAY;
        std::vector<std::pair<int, std::size_t>> stack{{root, 0}};  // frames {vertex, next index}
        while (!stack.empty()) {
            auto& [u, i] = stack.back();
            if (i < adj[u].size()) {
                int v = adj[u][i++];
                int from = u;  // copy: push_back below may invalidate the reference
                if (colour[v] == WHITE) {
                    r.classes[{from, v}] = "tree";
                    r.d[v] = ++time;
                    colour[v] = GRAY;
                    stack.emplace_back(v, 0);
                } else if (colour[v] == GRAY) {
                    r.classes[{from, v}] = "back";
                } else if (r.d[from] < r.d[v]) {
                    r.classes[{from, v}] = "forward";
                } else {
                    r.classes[{from, v}] = "cross";
                }
            } else {
                int done = u;
                stack.pop_back();
                r.f[done] = ++time;
                colour[done] = BLACK;
            }
        }
    }
    return r;
}

int main() {
    const int A = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7;
    std::vector<std::vector<int>> adj = {{B, E, C}, {D, E}, {F}, {A}, {D}, {C, E}, {F, H}, {G}};
    Result r = dfsClassify(adj);
    auto cls = [&r](int u, int v) { return r.classes.at(std::make_pair(u, v)); };
    assert((r.d == std::vector<int>{1, 2, 8, 3, 5, 9, 13, 14}));
    assert((r.f == std::vector<int>{12, 7, 11, 4, 6, 10, 16, 15}));
    assert(cls(D, A) == "back" && cls(F, C) == "back" && cls(H, G) == "back");
    assert(cls(A, E) == "forward");
    assert(cls(E, D) == "cross" && cls(F, E) == "cross" && cls(G, F) == "cross");
    int trees = 0;
    for (const auto& [edge, c] : r.classes) trees += (c == "tree");
    assert(trees == 6 && r.classes.size() == 13);
    for (int u = 0; u < 8; ++u)
        for (int v = 0; v < 8; ++v) assert(!(r.d[u] < r.d[v] && r.d[v] < r.f[u] && r.f[u] < r.f[v]));
    std::cout << "dfs classify OK\n";
}
const WHITE = 0;
const GRAY = 1;
const BLACK = 2;

function dfsClassify(adj: number[][]): { d: number[]; f: number[]; classes: Map<string, string> } {
  const n = adj.length;
  const colour = new Array<number>(n).fill(WHITE);
  const d = new Array<number>(n).fill(0);
  const f = new Array<number>(n).fill(0);
  const classes = new Map<string, string>();
  let time = 0;
  for (let root = 0; root < n; root++) {
    if (colour[root] !== WHITE) continue;
    d[root] = ++time;
    colour[root] = GRAY;
    const stack: [number, number][] = [[root, 0]]; // frames [vertex, next index]
    while (stack.length > 0) {
      const top = stack[stack.length - 1];
      const u = top[0];
      if (top[1] < adj[u].length) {
        const v = adj[u][top[1]++];
        const key = `${u},${v}`;
        if (colour[v] === WHITE) {
          classes.set(key, "tree");
          d[v] = ++time;
          colour[v] = GRAY;
          stack.push([v, 0]);
        } else if (colour[v] === GRAY) {
          classes.set(key, "back");
        } else if (d[u] < d[v]) {
          classes.set(key, "forward");
        } else {
          classes.set(key, "cross");
        }
      } else {
        stack.pop();
        f[u] = ++time;
        colour[u] = BLACK;
      }
    }
  }
  return { d, f, classes };
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const [A, B, C, D, E, F, G, H] = [0, 1, 2, 3, 4, 5, 6, 7];
const adj = [[B, E, C], [D, E], [F], [A], [D], [C, E], [F, H], [G]];
const { d, f, classes } = dfsClassify(adj);
check(d.join() === "1,2,8,3,5,9,13,14", "d");
check(f.join() === "12,7,11,4,6,10,16,15", "f");
check(classes.get(`${D},${A}`) === "back" && classes.get(`${F},${C}`) === "back" && classes.get(`${H},${G}`) === "back", "back");
check(classes.get(`${A},${E}`) === "forward", "forward");
check(classes.get(`${E},${D}`) === "cross" && classes.get(`${F},${E}`) === "cross" && classes.get(`${G},${F}`) === "cross", "cross");
check([...classes.values()].filter((c) => c === "tree").length === 6 && classes.size === 13, "counts");
for (let u = 0; u < 8; u++) {
  for (let v = 0; v < 8; v++) check(!(d[u] < d[v] && d[v] < f[u] && f[u] < f[v]), "parenthesis");
}
console.log("dfs classify OK");

Find a directed cycle (or prove there is none)

Three-colour iterative DFS with parent pointers. On a back edge , the cycle is , read off the parents. Returns the cycle as a vertex list starting and ending at the same vertex, or an empty list for a DAG.

def find_cycle(adj):
    n = len(adj)
    colour = [0] * n                      # 0 white, 1 gray, 2 black
    parent = [-1] * n
    for root in range(n):
        if colour[root]:
            continue
        colour[root] = 1
        stack = [(root, 0)]
        while stack:
            u, i = stack[-1]
            if i < len(adj[u]):
                stack[-1] = (u, i + 1)
                v = adj[u][i]
                if colour[v] == 0:
                    colour[v] = 1
                    parent[v] = u
                    stack.append((v, 0))
                elif colour[v] == 1:      # back edge u -> v closes a cycle
                    cycle = [u]
                    while cycle[-1] != v:
                        cycle.append(parent[cycle[-1]])
                    cycle.reverse()
                    return cycle + [v]
            else:
                colour[u] = 2
                stack.pop()
    return []


def is_cycle(adj, cyc):
    return len(cyc) >= 2 and cyc[0] == cyc[-1] and all(b in adj[a] for a, b in zip(cyc, cyc[1:]))


if __name__ == "__main__":
    g1 = [[1], [2], [3], [1], []]                       # 1 -> 2 -> 3 -> 1
    c = find_cycle(g1)
    assert is_cycle(g1, c) and sorted(set(c)) == [1, 2, 3]
    dag = [[1, 2], [3], [3], []]                        # diamond: cross edge, no cycle
    assert find_cycle(dag) == []
    assert find_cycle([[0]]) == [0, 0]                  # self-loop
    A, B, C, D, E, F, G, H = range(8)
    ex = [[B, E, C], [D, E], [F], [A], [D], [C, E], [F, H], [G]]
    assert find_cycle(ex) == [A, B, D, A]
    print("find cycle OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class FindCycle {
    static List<Integer> findCycle(int[][] adj) {
        int n = adj.length;
        int[] colour = new int[n], parent = new int[n];
        java.util.Arrays.fill(parent, -1);
        for (int root = 0; root < n; root++) {
            if (colour[root] != 0) continue;
            colour[root] = 1;
            ArrayDeque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[] {root, 0});
            while (!stack.isEmpty()) {
                int[] top = stack.peek();
                int u = top[0];
                if (top[1] < adj[u].length) {
                    int v = adj[u][top[1]++];
                    if (colour[v] == 0) {
                        colour[v] = 1;
                        parent[v] = u;
                        stack.push(new int[] {v, 0});
                    } else if (colour[v] == 1) {
                        List<Integer> cycle = new ArrayList<>();
                        cycle.add(u);
                        while (cycle.get(cycle.size() - 1) != v) cycle.add(parent[cycle.get(cycle.size() - 1)]);
                        Collections.reverse(cycle);
                        cycle.add(v);
                        return cycle;
                    }
                } else {
                    colour[u] = 2;
                    stack.pop();
                }
            }
        }
        return new ArrayList<>();
    }

    static boolean isCycle(int[][] adj, List<Integer> c) {
        if (c.size() < 2 || !c.get(0).equals(c.get(c.size() - 1))) return false;
        for (int i = 0; i + 1 < c.size(); i++) {
            boolean found = false;
            for (int w : adj[c.get(i)]) if (w == c.get(i + 1)) found = true;
            if (!found) return false;
        }
        return true;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[][] g1 = {{1}, {2}, {3}, {1}, {}};
        check(isCycle(g1, findCycle(g1)), "cycle");
        check(findCycle(new int[][] {{1, 2}, {3}, {3}, {}}).isEmpty(), "dag");
        check(findCycle(new int[][] {{0}}).equals(List.of(0, 0)), "self-loop");
        int[][] ex = {{1, 4, 2}, {3, 4}, {5}, {0}, {3}, {2, 4}, {5, 7}, {6}};
        check(findCycle(ex).equals(List.of(0, 1, 3, 0)), "example");
        System.out.println("find cycle OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

std::vector<int> findCycle(const std::vector<std::vector<int>>& adj) {
    int n = static_cast<int>(adj.size());
    std::vector<int> colour(n, 0), parent(n, -1);
    for (int root = 0; root < n; ++root) {
        if (colour[root]) continue;
        colour[root] = 1;
        std::vector<std::pair<int, std::size_t>> stack{{root, 0}};
        while (!stack.empty()) {
            int u = stack.back().first;
            std::size_t& i = stack.back().second;
            if (i < adj[u].size()) {
                int v = adj[u][i++];
                if (colour[v] == 0) {
                    colour[v] = 1;
                    parent[v] = u;
                    stack.emplace_back(v, 0);
                } else if (colour[v] == 1) {
                    std::vector<int> cycle{u};
                    while (cycle.back() != v) cycle.push_back(parent[cycle.back()]);
                    std::reverse(cycle.begin(), cycle.end());
                    cycle.push_back(v);
                    return cycle;
                }
            } else {
                colour[u] = 2;
                stack.pop_back();
            }
        }
    }
    return {};
}

bool isCycle(const std::vector<std::vector<int>>& adj, const std::vector<int>& c) {
    if (c.size() < 2 || c.front() != c.back()) return false;
    for (std::size_t i = 0; i + 1 < c.size(); ++i)
        if (std::find(adj[c[i]].begin(), adj[c[i]].end(), c[i + 1]) == adj[c[i]].end()) return false;
    return true;
}

int main() {
    std::vector<std::vector<int>> g1 = {{1}, {2}, {3}, {1}, {}};
    assert(isCycle(g1, findCycle(g1)));
    assert(findCycle({{1, 2}, {3}, {3}, {}}).empty());
    assert((findCycle({{0}}) == std::vector<int>{0, 0}));
    std::vector<std::vector<int>> ex = {{1, 4, 2}, {3, 4}, {5}, {0}, {3}, {2, 4}, {5, 7}, {6}};
    assert((findCycle(ex) == std::vector<int>{0, 1, 3, 0}));
    std::cout << "find cycle OK\n";
}
function findCycle(adj: number[][]): number[] {
  const n = adj.length;
  const colour = new Array<number>(n).fill(0);
  const parent = new Array<number>(n).fill(-1);
  for (let root = 0; root < n; root++) {
    if (colour[root] !== 0) continue;
    colour[root] = 1;
    const stack: [number, number][] = [[root, 0]];
    while (stack.length > 0) {
      const top = stack[stack.length - 1];
      const u = top[0];
      if (top[1] < adj[u].length) {
        const v = adj[u][top[1]++];
        if (colour[v] === 0) {
          colour[v] = 1;
          parent[v] = u;
          stack.push([v, 0]);
        } else if (colour[v] === 1) {
          const cycle = [u];
          while (cycle[cycle.length - 1] !== v) cycle.push(parent[cycle[cycle.length - 1]]);
          cycle.reverse();
          cycle.push(v);
          return cycle;
        }
      } else {
        colour[u] = 2;
        stack.pop();
      }
    }
  }
  return [];
}

function isCycle(adj: number[][], c: number[]): boolean {
  if (c.length < 2 || c[0] !== c[c.length - 1]) return false;
  for (let i = 0; i + 1 < c.length; i++) if (!adj[c[i]].includes(c[i + 1])) return false;
  return true;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const g1 = [[1], [2], [3], [1], []];
check(isCycle(g1, findCycle(g1)), "cycle");
check(findCycle([[1, 2], [3], [3], []]).length === 0, "dag");
check(findCycle([[0]]).join() === "0,0", "self-loop");
const ex = [[1, 4, 2], [3, 4], [5], [0], [3], [2, 4], [5, 7], [6]];
check(findCycle(ex).join() === "0,1,3,0", "example");
console.log("find cycle OK");

Variant: recursive DFS, and the iterative orders compared

The recursive version for reference (it produces the same times as the iterative code above), plus the three iterative strategies from the mechanics section on A: [B, C], B: [C, D].

import sys


def dfs_recursive(adj):
    n = len(adj)
    d, f = [0] * n, [0] * n
    time = 0

    def visit(u):
        nonlocal time
        time += 1
        d[u] = time
        for v in adj[u]:
            if not d[v]:
                visit(v)
        time += 1
        f[u] = time

    for u in range(n):
        if not d[u]:
            visit(u)
    return d, f


def order_naive(adj, s):            # push all, mark on pop
    stack, seen, out = [s], set(), []
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        out.append(u)
        stack.extend(v for v in adj[u] if v not in seen)
    return out


def order_mark_on_push(adj, s):     # BFS habit, wrong for DFS order
    stack, seen, out = [s], {s}, []
    while stack:
        u = stack.pop()
        out.append(u)
        for v in reversed(adj[u]):
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return out


def order_frames(adj, s):           # faithful
    seen, out, stack = {s}, [s], [(s, 0)]
    while stack:
        u, i = stack[-1]
        if i < len(adj[u]):
            stack[-1] = (u, i + 1)
            v = adj[u][i]
            if v not in seen:
                seen.add(v)
                out.append(v)
                stack.append((v, 0))
        else:
            stack.pop()
    return out


A, B, C, D = range(4)
small = [[B, C], [C, D], [], []]
assert order_frames(small, A) == [A, B, C, D]
assert order_naive(small, A) == [A, C, B, D]
assert order_mark_on_push(small, A) == [A, B, D, C]

ex = [[1, 4, 2], [3, 4], [5], [0], [3], [2, 4], [5, 7], [6]]
assert dfs_recursive(ex) == ([1, 2, 8, 3, 5, 9, 13, 14], [12, 7, 11, 4, 6, 10, 16, 15])

# A 50,000-vertex path: recursion needs a raised limit, the frame version does not.
n = 50_000
path = [[i + 1] for i in range(n - 1)] + [[]]
assert len(order_frames(path, 0)) == n
old = sys.getrecursionlimit()
sys.setrecursionlimit(n + 1000)
try:
    d, f = dfs_recursive(path)
    assert d[n - 1] == n and f[0] == 2 * n
finally:
    sys.setrecursionlimit(old)
print("orders OK")

Variant: components, flood fill and undirected cycles

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    comp = [-1] * n
    k = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        comp[s] = k
        stack = [s]
        while stack:                       # order is irrelevant here
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = k
                    stack.append(v)
        k += 1
    return k, comp


def flood_fill(image, sr, sc, colour):
    old = image[sr][sc]
    if old == colour:
        return image
    R, C = len(image), len(image[0])
    stack = [(sr, sc)]
    image[sr][sc] = colour
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C and image[nr][nc] == old:
                image[nr][nc] = colour
                stack.append((nr, nc))
    return image


def has_undirected_cycle(n, edges):
    adj = [[] for _ in range(n)]
    for idx, (u, v) in enumerate(edges):
        adj[u].append((v, idx))
        adj[v].append((u, idx))
    seen = [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]                  # (vertex, id of the edge used to enter it)
        while stack:
            u, via = stack.pop()
            for v, idx in adj[u]:
                if idx == via:
                    continue               # skip the edge we came in on (by id: safe for multigraphs)
                if seen[v]:
                    return True
                seen[v] = True
                stack.append((v, idx))
    return False


assert count_components(6, [(0, 1), (1, 2), (3, 4)])[0] == 3
assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
assert has_undirected_cycle(3, [(0, 1), (1, 2), (2, 0)])
assert not has_undirected_cycle(4, [(0, 1), (1, 2), (1, 3)])        # a tree
assert has_undirected_cycle(2, [(0, 1), (0, 1)])                    # parallel edges
print("components OK")

The undirected cycle check uses the "push" style, which is safe here only because of a subtle fact: a vertex is marked when pushed, and finding an already-marked vertex through an edge other than the entry edge means two distinct routes reach it from the root, which together contain a cycle. That reasoning does not need DFS order at all — the same test works with a queue.

Variant: iterative deepening, all paths and a Hamiltonian check

def iddfs(start, is_goal, neighbours, max_depth):
    """Returns (depth, nodes generated) of the shallowest goal, or (None, nodes)."""
    generated = 0

    def dls(state, limit):
        nonlocal generated
        generated += 1
        if is_goal(state):
            return True
        if limit == 0:
            return False
        return any(dls(nxt, limit - 1) for nxt in neighbours(state))

    for limit in range(max_depth + 1):
        if dls(start, limit):
            return limit, generated
    return None, generated


def all_paths_dag(graph):
    target, out, path = len(graph) - 1, [], [0]

    def go(u):
        if u == target:
            out.append(path[:])
            return
        for v in graph[u]:
            path.append(v)
            go(v)
            path.pop()                     # backtrack

    go(0)
    return out


def has_hamiltonian_path(n, edges):
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    on_path = [False] * n

    def extend(u, length):
        if length == n:
            return True
        for v in adj[u]:
            if not on_path[v]:
                on_path[v] = True
                if extend(v, length + 1):
                    return True
                on_path[v] = False         # backtrack
        return False

    for s in range(n):
        on_path[s] = True
        if extend(s, 1):
            return True
        on_path[s] = False
    return False


# Complete 10-ary tree, goal at depth 5 never matches: count the work of the full search.
depth, gen = iddfs((), lambda s: False, lambda s: [s + (i,) for i in range(10)], 5)
assert depth is None and gen == 123_456       # vs 111,111 nodes for one BFS sweep to depth 5
depth, _ = iddfs(0, lambda x: x == 13, lambda x: [2 * x + 1, 2 * x + 2], 10)
assert depth == 3                             # 0 -> 2 -> 6 -> 13 in the implicit binary tree

assert all_paths_dag([[1, 2], [3], [3], []]) == [[0, 1, 3], [0, 2, 3]]
assert len(all_paths_dag([[4, 3, 1], [3, 2, 4], [3], [4], []])) == 5

assert has_hamiltonian_path(4, [(0, 1), (1, 2), (2, 3)])            # a path graph
assert not has_hamiltonian_path(4, [(0, 1), (0, 2), (0, 3)])        # a star
print("iddfs and backtracking OK")

Real-world uses

  • Build systems and package managers. Make, Bazel, Gradle and npm detect dependency cycles and compute build orders with DFS finish order (or Kahn's algorithm); the error message "circular dependency detected: a → b → c → a" is a back edge plus a walk up the stack. See topological sort.
  • Garbage collection. The mark phase of mark-sweep collectors is a reachability traversal from the roots, often depth-first with an explicit mark stack (to avoid recursion on deep object graphs, exactly the conversion shown above); some collectors use pointer reversal (Deutsch–Schorr–Waite) to do it with no stack memory at all. See memory allocators.
  • Deadlock detection. Databases and operating systems maintain a wait-for graph (transaction waits for a lock held by ); a cycle is a deadlock, found by DFS, and the victim is chosen among the cycle's vertices. See how databases work and OS algorithms.
  • Compilers. Control-flow analysis numbers basic blocks in DFS postorder (reverse postorder is the standard iteration order for forward data-flow problems), identifies loops through back edges, and computes dominators; call-graph cycles reveal mutual recursion. Spreadsheet engines detect circular references the same way.
  • Networking. Finding bridges and articulation points (single points of failure) in a network topology is a DFS with low-links (connectivity); routing protocols such as BGP must avoid forwarding loops, which are cycles in the forwarding graph.
  • Image processing and games. Flood fill implements the paint-bucket tool, connected-component labelling of binary images, region growing, and "capture" rules in Go-like games (a group with no liberties). Maze generation by randomized DFS ("recursive backtracker") produces long, winding corridors.
  • Model checking and SAT. Explicit-state model checkers explore the state graph depth-first to find counterexample traces, and nested DFS detects accepting cycles for liveness properties; DPLL-style SAT solvers are depth-first backtracking over variable assignments.
  • File systems and the web. find, du and recursive copy walk directory trees depth-first; symbolic links can create cycles, which is why such tools track visited inodes.

Pitfalls & edge cases

  • Two colours in a directed graph. "Visited" alone cannot tell a back edge from a cross edge; you will report cycles in DAGs (the diamond 0→1, 0→2, 1→3, 2→3 triggers it). Use three colours.
  • Parent edge in an undirected graph. The edge back to the parent looks like a back edge; skip it. With parallel edges, skip by edge id, not by vertex, or a genuine 2-cycle is missed.
  • Disconnected graphs. A DFS from vertex 0 only sees its component. Loop over all vertices for components, cycle detection and topological sort.
  • Recursion depth. A path-shaped graph or a large grid overflows the default stack in every language (≈ 1000 in Python, ≈ 10,000 in Node). Use the frame-stack version or raise limits deliberately.
  • Naive iterative DFS where order matters. "Push all neighbours" reverses neighbour order and loses finish times; "mark on push" builds a tree that is not a DFS tree. Fine for reachability, wrong for classification, topological order and low-links.
  • Mutating the graph during traversal. Removing edges or vertices while iterating adjacency lists invalidates iterators (C++), throws ConcurrentModificationException (Java), or silently skips elements (Python lists).
  • Backtracking without undoing. Forgetting path.pop() / on_path[v] = False after the recursive call corrupts every subsequent branch.
  • Self-loops. A self-loop v → v is a back edge (v is gray when scanned) and a cycle of length 1; make sure your cycle printer handles a cycle of one vertex.
  • IDDFS on graphs with cycles. Without a visited set, IDDFS can loop or re-explore exponentially many paths. Use it on trees or with cycle checking along the current path.
  • Grid flood fill with the new colour equal to the old. If you mark by recolouring and the colours are equal, the fill never terminates (or terminates immediately, depending on the check). Return early.
  • Timestamps off by one. Use one counter for both discovery and finish; with separate counters the parenthesis property no longer holds.
  • Python closures. Inner recursive functions that rebind a counter need nonlocal; mutating a list works, rebinding an int does not.

Variations

  • Preorder, postorder, reverse postorder. Recording vertices at discovery gives preorder; at finish, postorder; reversing postorder gives a topological order of a DAG and the iteration order for many compiler analyses.
  • Three-colour DFS. The basis of cycle detection and topological sort.
  • Low-link DFS (Tarjan). Tracks the smallest discovery time reachable through the subtree plus one back edge; finds bridges, articulation points and SCCs in one pass (connectivity).
  • Kosaraju's SCC algorithm. Two DFS passes: finish order on , then DFS on the reversed graph in decreasing finish order.
  • Euler tour of a tree. Recording entry and exit times flattens a tree into an array so that subtrees become ranges — the bridge to segment trees and Fenwick trees on trees.
  • Hierholzer's algorithm. A DFS variant that consumes edges instead of vertices and builds an Eulerian circuit (Euler & Hamiltonian paths).
  • Depth-limited and iterative deepening DFS; IDA*. Bounded depth, repeated with growing bounds; IDA* bounds by instead of depth.
  • Backtracking. DFS over partial solutions with an "on path" set and undo steps; backtracking & recursion.
  • Randomized DFS. Shuffled neighbour order: maze generation, randomized algorithms.
  • Nested DFS. Detects accepting cycles in Büchi automata (model checking).

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Flood Fill (LeetCode 733) — Recolour the region of same-coloured pixels around a start pixel. Teaches the basic grid DFS and the equal-colour edge case.

Hint

If the new colour equals the old one, return immediately. Otherwise DFS (or stack) over 4-neighbours with the old colour. The variant above is a full solution.

2. Number of Islands (LeetCode 200) — Count groups of land cells. Teaches components on a grid and counting DFS starts.

Hint

Scan every cell; when you find unvisited land, increment the count and flood the whole island.

Solution
def num_islands(grid):
    g = [row[:] for row in grid]
    R, C = len(g), len(g[0])
    count = 0
    for r in range(R):
        for c in range(C):
            if g[r][c] != "1":
                continue
            count += 1
            g[r][c] = "0"
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    if 0 <= nx < R and 0 <= ny < C and g[nx][ny] == "1":
                        g[nx][ny] = "0"
                        stack.append((nx, ny))
    return count


g1 = [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]]
g2 = [["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"]]
assert num_islands(g1) == 1
assert num_islands(g2) == 3

time, worst-case stack.

3. Counting Rooms (CSES 1192) — Count rooms in a building map of walls and floor. Teaches the same at cells, where recursion will overflow.

Hint

Iterative flood fill; flatten coordinates to r * m + c for speed.

4. Max Area of Island (LeetCode 695) — Largest island by cell count. Teaches returning an aggregate from each component.

Hint

Count cells popped during each flood; keep the maximum.

5. Number of Provinces (LeetCode 547) — Components given as an adjacency matrix. Teaches DFS over a matrix representation ( is unavoidable here).

Hint

For each unvisited city, DFS scanning its whole matrix row.

6. Building Roads (CSES 1666) — Add the fewest roads to connect all cities and print them. Teaches that the answer is (number of components − 1) and how to pick representatives.

Hint

Find one representative per component; connect representative to representative .

7. Surrounded Regions (LeetCode 130) — Capture regions not connected to the border. Teaches flipping the question: flood from the border, then everything unmarked is captured.

Hint

DFS from every border O, marking safe cells. Then flip all unmarked Os to X and restore the marked ones.

8. Pacific Atlantic Water Flow (LeetCode 417) — Cells from which water can reach both oceans. Teaches reverse-direction traversal (climb uphill from each ocean) and intersecting two reachability sets.

Hint

Two multi-start DFS runs, one from each ocean's border cells, moving to neighbours with height the current. Answer: cells in both sets.

9. All Paths From Source to Target (LeetCode 797) — List every path from node 0 to node in a DAG. Teaches DFS as backtracking and output-sensitive cost.

Hint

No visited set is needed in a DAG. Append on entry, pop on exit, record the path at the target.

Solution
def all_paths_source_target(graph):
    target, out, path = len(graph) - 1, [], [0]

    def go(u):
        if u == target:
            out.append(path[:])
            return
        for v in graph[u]:
            path.append(v)
            go(v)
            path.pop()

    go(0)
    return out


assert all_paths_source_target([[1, 2], [3], [3], []]) == [[0, 1, 3], [0, 2, 3]]
assert sorted(all_paths_source_target([[4, 3, 1], [3, 2, 4], [3], [4], []])) == sorted(
    [[0, 4], [0, 3, 4], [0, 1, 3, 4], [0, 1, 2, 3, 4], [0, 1, 4]])

Time proportional to the total length of all paths, which can be .

10. Round Trip (CSES 1669) — Find and print a cycle in an undirected graph (at least 3 cities). Teaches undirected cycle extraction with parent pointers.

Hint

DFS with parents; on reaching a visited vertex other than the parent, walk parents back from the current vertex to it.

11. Find Eventual Safe States (LeetCode 802) — Vertices from which every path ends at a terminal vertex. Teaches three-colour DFS: a vertex is safe iff it is not on and cannot reach a cycle.

Hint

A vertex is unsafe if DFS from it reaches a gray vertex (a cycle) or an unsafe vertex. Memoize: black means safe.

Solution
def eventual_safe_nodes(graph):
    n = len(graph)
    state = [0] * n                  # 0 white, 1 gray (unsafe if still gray), 2 safe

    def safe(u):
        if state[u]:
            return state[u] == 2
        state[u] = 1
        for v in graph[u]:
            if not safe(v):
                return False         # u stays gray = unsafe
        state[u] = 2
        return True

    return [u for u in range(n) if safe(u)]


assert eventual_safe_nodes([[1, 2], [2, 3], [5], [0], [5], [], []]) == [2, 4, 5, 6]
assert eventual_safe_nodes([[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]) == [4]

. For nodes in a long chain, convert to the iterative frame form or raise the recursion limit.

12. Round Trip II (CSES 1678) — Find and print a directed cycle. Teaches back-edge cycle extraction; the find_cycle implementation above solves it.

Hint

Three colours; on a back edge , walk parents from up to , reverse, close with . Iterative to survive vertices.

13. Fox And Two Dots (Codeforces 510B) — Does a grid of coloured dots contain a same-colour cycle of length at least 4? Teaches undirected cycle detection on an implicit grid graph.

Hint

DFS over same-coloured cells, skipping the cell you came from; reaching an already-visited same-colour cell means a cycle (on a grid, any such cycle automatically has length at least 4).

14. Unique Paths III (LeetCode 980) — Count walks from start to end that cover every empty cell exactly once. Teaches Hamiltonian-path backtracking on a small grid.

Hint

Count the cells that must be covered. DFS with an on-path mark; at the end cell, count the path only if every cell was used.

Solution
def unique_paths_iii(grid):
    R, C = len(grid), len(grid[0])
    need = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] != -1:
                need += 1
            if grid[r][c] == 1:
                start = (r, c)
    g = [row[:] for row in grid]

    def go(r, c, left):
        if g[r][c] == 2:
            return 1 if left == 1 else 0
        saved, g[r][c] = g[r][c], -1          # mark on path
        total = 0
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < R and 0 <= nc < C and g[nr][nc] != -1:
                total += go(nr, nc, left - 1)
        g[r][c] = saved                       # backtrack
        return total

    return go(start[0], start[1], need)


assert unique_paths_iii([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 2, -1]]) == 2
assert unique_paths_iii([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 2]]) == 4
assert unique_paths_iii([[0, 1], [2, 0]]) == 0

Exponential in the number of cells, fine for the problem's limit of 20 cells.

15. Critical Connections in a Network (LeetCode 1192) — Find every edge whose removal disconnects the network. A preview of low-link DFS: discovery times plus the earliest time reachable by one back edge.

Hint

An edge to a DFS child is a bridge iff no vertex in 's subtree has a back edge to or above: low[v] > d[u]. Full treatment in the connectivity lesson.

Common mistakes & interview follow-ups

"Recursive or iterative?" Recursive is clearer; say so, then state the depth risk and offer the frame-stack conversion. Interviewers like hearing the depth number for the given constraints (" nodes in a chain will overflow Python's default 1000").

"Why three colours?" Because in a directed graph, an edge to a visited-and-finished vertex (cross or forward) is not a cycle; only an edge to a vertex still on the stack is. Draw the diamond.

"Return the cycle, not just yes/no." Keep parents; on the back edge , walk from up to .

"DFS or BFS for connected components?" Either: both are . DFS is shorter recursively; BFS never has depth issues. For a stream of edges, union-find.

"What is the space complexity of DFS?" for colours plus the stack depth, which is worst case (a path) — compare BFS's widest layer.

"How would you detect a cycle in a graph too big for memory?" Stream edges into union-find (undirected). For directed graphs, Kahn's algorithm needs only in-degree counts plus adjacency; external-memory DFS is hard, which is one reason people prefer Kahn at scale.

"When would you use IDDFS?" Huge or infinite trees, unknown depth, little memory, no visited set (game trees, puzzle search with IDA*). Quote the overhead: about .

Mistakes interviewers watch for: two colours on directed graphs; not skipping the parent edge; forgetting to restart from unvisited vertices; missing the backtrack step; recursion depth on large inputs; mark-on-push iterative DFS used for topological order.

Quick quiz

1. In the trace, the edge A→E is scanned when E is already black. Why is it a forward edge and not a cross edge?

Answer

Because : E was discovered after A and inside A's interval (E is A's descendant, via B). A cross edge goes to a vertex discovered before the source and already finished, like E→D with .

2. Can an undirected graph's DFS produce a cross edge? Why?

Answer

No. For an edge with , is white and adjacent at , so it becomes 's descendant (white-path theorem). The edge is then either the tree edge that discovered or, scanned from , a back edge to the gray .

3. Recursive DFS on A: [B, C], B: [C, D] visits A, B, C, D. What order does "mark on push" iterative DFS produce, and why is the result not a DFS tree?

Answer

A, B, D, C. C is marked while A is processed, so B cannot discover it; C's parent becomes A. But at , C was white and adjacent to B, so by the white-path theorem a DFS tree must have C as B's descendant.

4. IDDFS on a tree with branching factor 2 and goal depth 10 generates how many nodes, compared with BFS?

Answer

versus for BFS: about 2×, the overhead for . Memory is instead of .

5. You need the recursion depth of DFS on a grid of open cells. What is the worst case, and what do you do in Python?

Answer

Up to (a snake-like DFS path can visit every cell before backtracking). Use the iterative frame-stack (or plain stack, for flood fill), rather than relying on sys.setrecursionlimit.

Further reading / sources

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th ed., §20.3 "Depth-first search" (parenthesis theorem, white-path theorem, edge classification) and §20.4 "Topological sort".
  • Robert Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1(2), 1972.
  • John Hopcroft and Robert Tarjan, "Efficient planarity testing", Journal of the ACM 21(4), 1974; and "Algorithm 447: Efficient algorithms for graph manipulation", Communications of the ACM 16(6), 1973.
  • Richard E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search", Artificial Intelligence 27(1), 1985.
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., §4.1 (DepthFirstSearch, connected components) and §4.2 (directed cycles, DFS orders).
  • Steven S. Skiena, The Algorithm Design Manual, 3rd ed., §7.8–7.10 (DFS, applications, DFS on directed graphs).
  • cp-algorithms: Depth First Search and Checking a graph for acyclicity and finding a cycle.
  • Édouard Lucas, Récréations mathématiques, vol. 1 (1882), which records Trémaux's maze-solving method; Maze-solving algorithm on Wikipedia for a summary.
  • Python documentation: sys.setrecursionlimit.

Previous lesson: BFS in Depth · Next lesson: Topological Sort & DAG DP

Related: Graphs overview · Graph Modeling · Stacks · Recursion & Induction · Backtracking & Recursion · Connectivity · LCA & Binary Lifting · Course home