DFS Visualization for Coding Interviews

Recursive explore; discovery/finish time coloring.

Concept

Depth-First Search dives as far as it can down one branch before backtracking to try the next. That single behavioral difference from BFS unlocks a completely different class of problems: cycle detection, topological ordering, strongly connected components, bridges and articulation points, and any tree DP that needs post-order aggregation. The elegance of DFS is that it gives you two natural time coordinates per vertex - a discovery time the moment you first step onto it, and a finish time the moment you back out of its subtree. Those timestamps expose the tree structure of the traversal and let you classify every edge as tree, back, forward, or cross. Whenever an algorithm claims to work in linear time on a graph and does something structural (ordering, component finding, reachability, ancestry), DFS is almost certainly underneath. Runtime is O(V+E) on an adjacency list, space is O(V) for the recursion stack or an explicit stack and two timestamp arrays.

How it works

Maintain a global clock that ticks each time you enter or exit a vertex. On visit(u), bump the clock and stamp disc[u]. For each neighbor v, if v is unvisited, recurse into it; that recursive call produces the tree edge (u, v). When recursion returns from every child, bump the clock again and stamp finish[u]. Two lemmas make timestamps powerful. First, the parenthesis theorem: for any two vertices u and v, the intervals [disc[u], finish[u]] and [disc[v], finish[v]] are either disjoint or one fully contains the other; they never partially overlap. Second, u is an ancestor of v in the DFS tree if and only if [disc[u], finish[u]] contains [disc[v], finish[v]]. Together these give you O(1) ancestor checks and make edge classification trivial: a back edge points to an ancestor (disc[v] < disc[u] and finish[v] unset), a forward edge points into your own subtree (disc[v] > disc[u] and finish[v] set), a cross edge points elsewhere (finish[v] set and disc[v] < disc[u]). Reversed finish order is a topological sort on a DAG. For an iterative version, simulate the call stack with an explicit Deque of (vertex, neighborIterator) pairs to avoid blowing the JVM stack on deep graphs.

Implementation

import java.util.*;

public class DFS {
    private final List<List<Integer>> adj;
    private final int[] disc;
    private final int[] finish;
    private int clock;

    public DFS(List<List<Integer>> adj) {
        this.adj = adj;
        int n = adj.size();
        this.disc = new int[n];
        this.finish = new int[n];
        Arrays.fill(disc, -1);
        Arrays.fill(finish, -1);
        this.clock = 0;
    }

    /** Run DFS from src and fill disc[]/finish[] for the reachable component. */
    public void dfs(int src) {
        visit(src);
    }

    private void visit(int u) {
        disc[u] = clock++;
        for (int v : adj.get(u)) {
            if (disc[v] == -1) visit(v);           // tree edge
            // else v is either ancestor (back), descendant (forward), or cross edge
        }
        finish[u] = clock++;
    }

    /** Full DFS across every component, returning reverse-finish order. */
    public int[] dfsAll() {
        int n = adj.size();
        for (int s = 0; s < n; s++) if (disc[s] == -1) visit(s);
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(finish[b], finish[a]));
        int[] out = new int[n];
        for (int i = 0; i < n; i++) out[i] = order[i];
        return out;
    }

    public int[] discovery() { return disc; }
    public int[] finishTimes() { return finish; }

    /** u is an ancestor of v in the DFS tree iff disc[u] <= disc[v] and finish[v] <= finish[u]. */
    public boolean isAncestor(int u, int v) {
        return disc[u] <= disc[v] && finish[v] <= finish[u];
    }
}

Complexity

• Time: O(V + E)
• Space: O(V)

Common pitfalls

• Recursing on a graph with tens of thousands of vertices and blowing the default JVM stack - convert to an explicit stack for production.
• Forgetting to start DFS from every unvisited vertex when the graph is disconnected.
• Confusing an undirected back edge with the parent edge; you must skip the edge back to the immediate parent, not all visited vertices.
• Using disc[v] != -1 as a synonym for "v is finished" - a vertex on the current DFS path has disc set but finish still -1.
• Assuming reverse-finish order is a valid topological sort when the graph has a cycle; it only works on DAGs.

Key design decisions & trade-offs

• Recursive vs iterative — Chosen: Recursive for clarity, iterative for depth safety. Recursion reads like the algorithm; an explicit stack survives arbitrary graph depth without -Xss tuning.
• Timestamp encoding — Chosen: Two separate arrays disc[] and finish[]. Keeps ancestor and edge-classification queries O(1) and is cheaper than reconstructing order from a single visit log.

Practice problems

• Clone Graph

Interview follow-ups

• Topological sort via reverse finish order on a DAG.
• Cycle detection using a three-color (white/gray/black) DFS.
• Bridges and articulation points via Tarjan's low-link values.
• Strongly connected components via Kosaraju (two DFS passes) or Tarjan.
• Iterative DFS with an explicit Deque<StackFrame> for very deep graphs.

Why it matters

DFS is a core part of the Graphs toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related

• BFS
• Topological Sort
• Tarjan SCC