DFS: Depth-First Search In Depth

March 2026 · 20 min read

DFS dives as deep as possible into the graph before backtracking. Where BFS explores level by level (breadth), DFS explores branch by branch (depth). This behavior makes DFS the natural choice for problems involving paths, cycles, connected components, and anything that benefits from exploring one direction fully before trying another.

The Core Idea

Think of exploring a maze. At every junction, you pick one unexplored path and follow it. When you hit a dead end, you backtrack to the last junction and try the next path. That is DFS.

DFS naturally uses a stack. Recursion provides an implicit stack (the call stack), which is why recursive DFS is the most common form. You can also write it iteratively with an explicit stack.

The Algorithm

Recursive DFS

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    // Process node here (pre-order)

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
    // Post-processing here (post-order)
}

The recursion handles the stack implicitly. Each recursive call pushes a frame. When it returns, it backtracks (pops the frame).

Iterative DFS

void dfs_iterative(int source, vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;

    st.push(source);

    while (!st.empty()) {
        int node = st.top();
        st.pop();

        if (visited[node]) continue;
        visited[node] = true;
        // Process node

        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                st.push(neighbor);
            }
        }
    }
}

Visual Step-by-Step Walkthrough

Tracing recursive DFS on the same graph, starting from node 0. Neighbors are processed in ascending order.

Edge Classification

During DFS on a directed graph, every edge falls into one of four categories. This classification is essential for cycle detection and topological sort.

To classify edges, use a coloring scheme:

• White: unvisited node.
• Gray: currently in the recursion stack (entered but not yet exited).
• Black: fully processed (entered and exited).

enum Color { WHITE, GRAY, BLACK };
vector<Color> color(n, WHITE);

void dfs(int u) {
    color[u] = GRAY;  // entering
    for (int v : adj[u]) {
        if (color[v] == WHITE) {
            // Tree edge: u -> v
            dfs(v);
        } else if (color[v] == GRAY) {
            // Back edge: u -> v (CYCLE!)
        } else {
            // Forward or cross edge
        }
    }
    color[u] = BLACK;  // exiting
}

Pre-order and Post-order in DFS

DFS visits each node twice: once when entering (discovery) and once when exiting (finishing). This gives two orderings:

• Pre-order (discovery time): the order in which nodes are first visited. Useful for tree serialization, DFS numbering.
• Post-order (finish time): the order in which nodes are fully processed (all descendants done). Useful for topological sort (reverse post-order), SCC algorithms.

int timer = 0;
vector<int> disc(n), fin(n);

void dfs(int u) {
    disc[u] = timer++;  // pre-order timestamp
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
    fin[u] = timer++;  // post-order timestamp
}

For our graph (DFS from 0, neighbors ascending):

Interactive Animation

Common DFS Patterns

Connected Components

int components = 0;
vector<bool> visited(n, false);
for (int i = 0; i < n; i++) {
    if (!visited[i]) {
        dfs(i, adj, visited);
        components++;
    }
}

Cycle Detection (Directed Graph)

Use the gray/black coloring from above. A back edge (edge to a gray node) means a cycle exists.

Flood Fill

DFS on a grid. Start at a cell, visit all connected cells of the same color. Classic "number of islands" problem.

void floodFill(vector<vector<int>>& grid, int r, int c, int color) {
    if (r < 0 || r >= m || c < 0 || c >= n) return;
    if (grid[r][c] != oldColor) return;
    grid[r][c] = color;
    floodFill(grid, r+1, c, color);
    floodFill(grid, r-1, c, color);
    floodFill(grid, r, c+1, color);
    floodFill(grid, r, c-1, color);
}

Complexity

• Time: O(V + E). Each vertex visited once. Each edge examined once.
• Space: O(V). Visited array + recursion stack (or explicit stack). Worst case recursion depth is V (a straight-line graph).

Common Mistakes

• Forgetting the visited check. Infinite loop on graphs with cycles.
• Stack overflow on large inputs. Recursive DFS on a chain of 10⁶ nodes will crash. Switch to iterative.
• Confusing directed and undirected cycle detection. In undirected graphs, the parent edge is not a back edge. Track the parent to avoid false positives.