33.02Intermediate / Advanced5 topics18 min5 interactive animations

Depth-first search

Depth-first search follows one path as deep as it can, then backs up: it is recursion on a graph, and the order in which it enters and leaves vertices reveals the graph's structure.

Learning goals

Write DFS recursively and with an explicit stack and relate the two
Record discovery and finish times
Describe the DFS tree and test ancestry with the times
Use white, grey and black colours to describe where a vertex is in the search

Prerequisites

Breadth-first searchRecursionStacks

Walking through a maze, you keep taking a corridor until it dead-ends and then go back to the last junction with an unexplored branch. DFS does the same, and the moment you leave a vertex is exactly when everything reachable from it has been explored.

33.02.1

Recursive DFS

Recursive DFS marks the vertex, then calls itself on each unvisited neighbour. The call stack holds the path from the start to the current vertex. When a call returns, the search backs up one step to the vertex that called it and tries its next neighbour.

Run *Recursive DFS: discovery and finish times* and watch the current vertex travel down a path, hit a dead end and come back. Like BFS the total work is O(n + m), but the recursion depth can reach n, which can overflow Java's stack on a long path.

Java

1static List<Integer> dfsOrderRec(List<List<Integer>> g, int s) {   // preorder: the order vertices are first entered
2    List<Integer> order = new ArrayList<>();
3    visit(g, s, new boolean[g.size()], order);
4    return order;
5}
6static void visit(List<List<Integer>> g, int u, boolean[] seen, List<Integer> order) {
7    seen[u] = true;
8    order.add(u);
9    for (int v : g.get(u))
10        if (!seen[v]) visit(g, v, seen, order);
11}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

33.02.2

Iterative DFS

To avoid deep recursion, keep the stack yourself. Pushing all neighbours at once and popping the last one visits vertices in a valid depth-first order but a *different* order from the recursive version. To reproduce the recursive order exactly, store with each stack entry how far through its neighbour list you are, and push only one neighbour at a time.

The animation's *explicit stack* variant shows the stack contents. The stack never holds more than one entry per vertex here, so memory is O(n) and Java's call-stack limit no longer matters.

Java

1static List<Integer> dfsOrderIter(List<List<Integer>> g, int s) {   // same order as the recursive version
2    boolean[] seen = new boolean[g.size()];
3    int[] next = new int[g.size()];                  // next[u] = how many neighbours of u have been tried
4    List<Integer> order = new ArrayList<>();
5    Deque<Integer> stack = new ArrayDeque<>();
6    seen[s] = true;
7    order.add(s);
8    stack.push(s);
9    while (!stack.isEmpty()) {
10        int u = stack.peek();
11        if (next[u] < g.get(u).size()) {
12            int v = g.get(u).get(next[u]++);
13            if (!seen[v]) { seen[v] = true; order.add(v); stack.push(v); }
14        } else {
15            stack.pop();                             // u is finished: back up
16        }
17    }
18    return order;
19}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

33.02.3

Discovery/finish time

Keep a clock that ticks each time a vertex is entered or left. The **discovery time** disc[u] is the tick when u is first entered and the **finish time** fin[u] is the tick when the search leaves it for the last time. The interval [disc[u], fin[u]] of a vertex always either contains or is disjoint from another's interval (the *parenthesis theorem*), never partly overlapping.

These times answer ancestry questions in O(1) and are the raw material for topological sorting and strongly connected components in later chapters. The animation labels each vertex with its two times.

Java

1static int clock;
2static int[][] dfsTimes(List<List<Integer>> g) {           // {disc, fin}; each tick of the clock enters or leaves a vertex
3    int n = g.size();
4    int[] disc = new int[n], fin = new int[n];
5    Arrays.fill(disc, -1);
6    clock = 0;
7    for (int s = 0; s < n; s++)
8        if (disc[s] == -1) timeVisit(g, s, disc, fin);
9    return new int[][]{disc, fin};
10}
11static void timeVisit(List<List<Integer>> g, int u, int[] disc, int[] fin) {
12    disc[u] = clock++;
13    for (int v : g.get(u))
14        if (disc[v] == -1) timeVisit(g, v, disc, fin);
15    fin[u] = clock++;
16}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

33.02.4

DFS tree

Each time DFS discovers a vertex from a neighbour, it records that edge as a **tree edge**. The tree edges form the **DFS tree**; if the graph is not connected (or a directed graph is not reachable from one vertex), the search restarts and you get a **DFS forest**. A vertex u is an ancestor of v exactly when disc[u] <= disc[v] and fin[v] <= fin[u].

Unlike the BFS tree, a DFS tree is usually long and thin, and its paths are not shortest. What it does capture is the nesting of the search, which is why it classifies edges and finds cycles.

Java

1static class DfsForest {
2    final int[] parent, disc, fin;
3    private int clock = 0;
4    DfsForest(List<List<Integer>> g) {
5        int n = g.size();
6        parent = new int[n]; disc = new int[n]; fin = new int[n];
7        Arrays.fill(parent, -1);
8        Arrays.fill(disc, -1);
9        for (int s = 0; s < n; s++)
10            if (disc[s] == -1) go(g, s);
11    }
12    private void go(List<List<Integer>> g, int u) {
13        disc[u] = clock++;
14        for (int v : g.get(u))
15            if (disc[v] == -1) { parent[v] = u; go(g, v); }        // (u, v) is a tree edge
16        fin[u] = clock++;
17    }
18    boolean isAncestor(int u, int v) { return disc[u] <= disc[v] && fin[v] <= fin[u]; }
19}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

33.02.5

Visited colors

A boolean seen array is enough to visit each vertex once, but three states say more. **White** means not yet discovered, **grey** means discovered and still being explored (it is on the recursion stack), and **black** means finished. A vertex is grey from its discovery time until its finish time.

The grey vertices always form a single path from the root of the current tree down to the current vertex, so the grey set *is* the recursion stack. This is the key fact behind directed cycle detection in the next lesson. The *three colours* option in the animation colours vertices this way.

Java

1static List<Integer> greyStackAt(List<List<Integer>> g, int s, int target) {   // grey vertices when target is discovered
2    int[] colour = new int[g.size()];                // 0 white, 1 grey, 2 black
3    List<Integer> stack = new ArrayList<>();         // the grey vertices, in order of discovery
4    List<Integer> found = new ArrayList<>();
5    colourVisit(g, s, target, colour, stack, found);
6    return found;
7}
8static void colourVisit(List<List<Integer>> g, int u, int target, int[] colour, List<Integer> stack, List<Integer> found) {
9    colour[u] = 1;
10    stack.add(u);
11    if (u == target && found.isEmpty()) found.addAll(stack);
12    for (int v : g.get(u))
13        if (colour[v] == 0) colourVisit(g, v, target, colour, stack, found);
14    stack.remove(stack.size() - 1);
15    colour[u] = 2;
16}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph
Flood Fill

Medium

Clone Graph
All Paths From Source to Target
Keys and Rooms

Advanced

Critical Connections in a Network
Reconstruct Itinerary

Key takeaways

DFS goes deep first; recursion or an explicit stack both give O(n + m) time.
Discovery and finish times nest like parentheses and answer ancestry in O(1).
DFS tree paths are not shortest paths; use BFS for fewest edges.
White, grey and black describe unvisited, on the stack and finished; the grey vertices form the current path.