Depth-First Search (DFS)

A Bit of History

Long before computers existed, French mathematician Charles Pierre Trémaux described a method in the 1880s for escaping an arbitrary maze without a map: mark every passage you walk through, never re-enter a passage that has been marked twice, and when every passage from your current junction has already been tried, backtrack the way you came. That is, structurally, exactly depth-first search — a stack (your memory of "the way back") replacing a physical trail of chalk marks. The algorithm was formalized for graphs in the 20th century and became a cornerstone of computer science through the work of researchers like John Hopcroft and Robert Tarjan, whose 1970s papers on DFS-based algorithms (finding bridges, articulation points, and strongly connected components — all previewed here, formalized in Part 8) are still taught essentially unchanged today.

Working Principle

Depth-First Search explores as far as possible along each branch before backtracking. Unlike BFS's queue, DFS uses a stack (LIFO) — either explicitly, or implicitly via function-call recursion. Starting from a source vertex, DFS visits it, then recursively visits an unvisited neighbor, then that neighbor's unvisited neighbor, and so on — only backing up (popping the stack) once a dead end (no unvisited neighbors) is reached.

def dfs_pseudocode(graph, u, visited=None):
    """
    Precondition: `graph` maps each vertex to a list of neighbors.
    Postcondition: every vertex reachable from u has been visited exactly once.
    """
    if visited is None:
        visited = set()
    visited.add(u)
    for v in graph[u]:
        if v not in visited:
            dfs_pseudocode(graph, v, visited)   # recursive call = implicit stack push
    return visited

Interactive Demo

The same 6-node graph from the BFS deep dive — step forward past the BFS scenes to see DFS explore it instead. Notice how DFS commits to node D (a dead end) before ever touching C, while BFS visited both at the same "layer."

Discovery/Finish Times & Edge Classification

A refinement that unlocks most of DFS's advanced applications: stamp each vertex with a discovery time \(d[v]\) (when it's first visited) and a finish time \(f[v]\) (when the recursive call over all its neighbors returns). Every edge \((u,v)\) encountered during the search then falls into exactly one of four categories:

Complexity Analysis

Identical to BFS's argument, just with a stack instead of a queue: each vertex is pushed and popped exactly once, and each edge is examined at most twice (undirected) or once (directed).

$$\text{Time: } O(V + E) \qquad \text{Space: } O(V) \text{ for the visited set and the recursion/explicit stack}$$

Implementation

from collections import defaultdict

def dfs_recursive(adj, source):
    """Recursive DFS. Returns the visit order (like a Tremaux thread)."""
    visited = set()
    order = []

    def visit(u):
        visited.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                visit(v)

    visit(source)
    return order

def dfs_iterative(adj, source):
    """Iterative DFS using an explicit stack — avoids recursion-depth limits."""
    visited = {source}
    stack = [source]
    order = []

    while stack:
        u = stack.pop()          # LIFO: most recently pushed vertex first
        order.append(u)
        for v in reversed(adj[u]):     # reversed to match recursive visit order
            if v not in visited:
                visited.add(v)
                stack.append(v)

    return order

adj = defaultdict(list, {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "E", "F"],
    "D": ["B"], "E": ["B", "C"], "F": ["C"],
})

print("Recursive DFS order:", dfs_recursive(adj, "A"))
print("Iterative DFS order:", dfs_iterative(adj, "A"))

#include <vector>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std;

void dfsRecursive(unordered_map<string, vector<string>>& adj,
                   const string& u, unordered_set<string>& visited,
                   vector<string>& order) {
    visited.insert(u);
    order.push_back(u);
    for (const string& v : adj[u]) {
        if (!visited.count(v)) {
            dfsRecursive(adj, v, visited, order);
        }
    }
}

vector<string> dfsIterative(unordered_map<string, vector<string>>& adj,
                             const string& source) {
    unordered_set<string> visited{source};
    stack<string> s;
    s.push(source);
    vector<string> order;

    while (!s.empty()) {
        string u = s.top(); s.pop();
        order.push_back(u);
        for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
            if (!visited.count(*it)) {
                visited.insert(*it);
                s.push(*it);
            }
        }
    }
    return order;
}

int main() {
    unordered_map<string, vector<string>> adj = {
        {"A", {"B", "C"}}, {"B", {"A", "D", "E"}}, {"C", {"A", "E", "F"}},
        {"D", {"B"}}, {"E", {"B", "C"}}, {"F", {"C"}}
    };

    unordered_set<string> visited;
    vector<string> order;
    dfsRecursive(adj, "A", visited, order);

    cout << "Recursive DFS visited " << order.size() << " vertices" << endl;
    return 0;
}

import java.util.*;

class DFS {
    static void dfsRecursive(Map<String, List<String>> adj, String u,
                              Set<String> visited, List<String> order) {
        visited.add(u);
        order.add(u);
        for (String v : adj.getOrDefault(u, Collections.emptyList())) {
            if (!visited.contains(v)) {
                dfsRecursive(adj, v, visited, order);
            }
        }
    }

    static List<String> dfsIterative(Map<String, List<String>> adj, String source) {
        Set<String> visited = new HashSet<>(List.of(source));
        Deque<String> stack = new ArrayDeque<>();
        stack.push(source);
        List<String> order = new ArrayList<>();

        while (!stack.isEmpty()) {
            String u = stack.pop();
            order.add(u);
            List<String> neighbors = adj.getOrDefault(u, Collections.emptyList());
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                String v = neighbors.get(i);
                if (!visited.contains(v)) {
                    visited.add(v);
                    stack.push(v);
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Map<String, List<String>> adj = new HashMap<>();
        adj.put("A", Arrays.asList("B", "C"));
        adj.put("B", Arrays.asList("A", "D", "E"));
        adj.put("C", Arrays.asList("A", "E", "F"));
        adj.put("D", Arrays.asList("B"));
        adj.put("E", Arrays.asList("B", "C"));
        adj.put("F", Arrays.asList("C"));

        List<String> order = new ArrayList<>();
        dfsRecursive(adj, "A", new HashSet<>(), order);
        System.out.println("Recursive DFS order: " + order);
    }
}

Real-World Applications

Beyond mazes, DFS underlies: topological sorting (Part 7 — order tasks so dependencies come first, using reverse finish-time order), cycle detection in build systems and package managers (detecting circular dependencies), flood fill in image editors (the "paint bucket" tool), and finding connected components, bridges, and articulation points — critical infrastructure and network-reliability analysis (Part 8).

Exercises

1. Trace DFS by hand on the graph \(A\text{-}B, B\text{-}C, C\text{-}A, C\text{-}D\) starting at \(A\), listing discovery and finish times for every vertex.
2. Explain why a back edge can only exist in the direction "descendant discovers an ancestor still on the stack," never the reverse.
3. Modify the iterative DFS code above to also record each vertex's parent, then write a function to reconstruct the path from the source to any visited vertex.
4. Challenge: Adapt DFS to detect a cycle in a directed graph using three vertex states (white/unvisited, gray/on-stack, black/finished) instead of a single visited set, and explain why a single boolean visited flag is insufficient for directed cycle detection (hint: consider a cross edge to an already-finished vertex versus a back edge to a gray vertex).

Limitations