Depth-First Search

What Is DFS?

Depth-First Search (DFS) is a graph traversal algorithm — a systematic way to visit every node in a graph (a collection of nodes connected by edges). DFS picks a direction and follows it as far as possible before backing up. Think of exploring a maze by always turning right until you hit a dead end, then retracing your steps to the last fork and trying a different path.

The idea is ancient. French mathematician Charles Pierre Trémaux described a version of it in the 19th century as a strategy for solving mazes. You mark where you've been, go as deep as you can, and backtrack when stuck. Computer scientists formalized it in the 1970s — Tarjan and Hopcroft built some of the most elegant graph algorithms on top of DFS, including bridge-finding and strongly connected components.

DFS uses a stack — either the call stack (via recursion, where the programming language tracks function calls automatically) or an explicit stack data structure you manage yourself. The stack remembers where to go back to when you hit a dead end. This is the fundamental difference from BFS (Breadth-First Search), which uses a queue and explores level by level instead of diving deep.

Two Important Timestamps

DFS assigns each node two timestamps that encode a lot of structural information:

• Discovery time (d): When DFS first visits the node — the moment it "discovers" it
• Finish time (f): When DFS is done with the node and all its descendants (nodes reachable by following edges forward)

These timestamps tell you about the graph's structure. If node A's interval [d_A, f_A] completely contains node B's interval [d_B, f_B], then B is a descendant of A in the DFS tree. This is called the parenthesis theorem — the intervals either nest perfectly or don't overlap at all, like properly matched parentheses.

Why DFS Instead of BFS?

BFS and DFS both visit every node. The difference is how they explore, and that changes what problems each one solves naturally:

• DFS is natural for problems with recursive structure. Tree height, path existence, backtracking — these all decompose into "solve for children, combine results." DFS maps directly to recursion.
• DFS uses less memory on wide graphs. BFS stores an entire frontier level in its queue. On a tree with branching factor b and depth d, BFS needs O(b^d) space. DFS only needs O(d) — it just stores the current path.
• DFS finds cycles and ordering. The timestamps and edge classification (covered below) give you cycle detection and topological sort essentially for free.

Where DFS Shows Up

• Topological sort: Order tasks so that dependencies come first (build systems, course prerequisites). This requires a DAG — a Directed Acyclic Graph, meaning no cycles.
• Cycle detection: Finding back edges (edges pointing to an ancestor in the DFS tree) in directed graphs reveals cycles
• Connected components: In undirected graphs, each DFS run from an unvisited node discovers one connected component — a maximal group of nodes where every node is reachable from every other
• Strongly connected components: Tarjan's and Kosaraju's algorithms both use DFS to find SCCs in directed graphs — maximal groups where every node can reach every other node following directed edges
• Maze generation: Randomized DFS creates mazes with long, winding paths
• Backtracking: N-Queens, Sudoku solvers, permutation generation — all DFS at heart
• Bridge and articulation point finding: Tarjan's bridge algorithm uses DFS discovery times to find edges and nodes whose removal disconnects the graph

How It Works

Recursive DFS

1. Visit the current node. Mark it as visited. Record its discovery time.
2. Recurse on each unvisited neighbor. The function calls itself for every adjacent node it hasn't seen.
3. Backtrack when all neighbors are visited. Record the finish time. The function returns, and the call stack unwinds to the previous node.

Simple and clean. The call stack handles backtracking automatically — when a recursive call returns, you're back at the parent. The downside: deep graphs can overflow the stack. Python's default recursion limit is 1000 (you can check with sys.getrecursionlimit()). A chain graph with 10,000 nodes will crash.

Iterative DFS

1. Push the start node onto an explicit stack (a data structure you create, not the call stack).
2. Pop the top node. If not visited, mark it visited and process it.
3. Push all unvisited neighbors onto the stack.
4. Repeat until the stack is empty.

No recursion limit issues, but computing discovery/finish times is trickier — you need to push sentinel markers onto the stack to know when to record finish times. Use the iterative version when the graph might be deep (10,000+ nodes) or when you want explicit control over the traversal.

Edge Classification

DFS classifies every edge in the graph into one of four types. This classification is central to cycle detection and topological sort:

• Tree edge: Leads to an unvisited node. These edges form the DFS tree (or DFS forest if the graph is disconnected).
• Back edge: Points to an ancestor (a node earlier on the current DFS path) in the DFS tree. A back edge means there's a cycle. This is the key insight for cycle detection.
• Forward edge: Points to a descendant that was already discovered via a different path. Only shows up in directed graphs.
• Cross edge: Points to a node in a different subtree — one that was fully processed before the current subtree. Only in directed graphs.

You can classify edges using the node colors/states during DFS. When you encounter a neighbor that's:

• Unvisited → tree edge
• In-progress (discovered but not finished) → back edge
• Completed (finished) → forward or cross edge (compare discovery times to distinguish)

DFS on Trees vs Graphs

On trees, DFS is simpler because there are no cycles and no "visited" check needed (just don't revisit the parent). Most binary tree problems — height, diameter, path sum, lowest common ancestor — are DFS by nature. You recurse on children, combine results, return up.

On general graphs, you need the visited set. Without it, a cycle sends DFS into an infinite loop. This is a mistake beginners make constantly.

Interactive Visualization

Click any node to start DFS. Watch the algorithm dive deep along one branch before backtracking. Nodes show discovery/finish times (d/f). The stack contents update on the right. Backtracking edges are shown in red.

Common Mistakes

Complexity Analysis

Time is identical to BFS: O(V + E) with adjacency lists. Here V is the number of vertices (nodes) and E is the number of edges. You visit each vertex once and scan its adjacency list once, giving V + E total work.

The space difference between DFS and BFS is in what they store. DFS keeps only the current path on the stack — O(V) worst case for a chain graph, but often much less. BFS stores an entire frontier level in the queue, which can be O(V) on the last level of a complete binary tree. For trees specifically, DFS space is O(h) where h is the height. On a balanced tree that's O(log n). On a completely skewed tree (basically a linked list), it's O(n).

Implementation

Recursive DFS

def dfs(graph, node, visited=None):
    """Basic recursive DFS on an adjacency list.
    
    graph: dict mapping each node to a list of its neighbors
           e.g. {0: [1, 2], 1: [3], 2: [3], 3: []}
    node:  starting node
    visited: set of already-visited nodes (created on first call)
    """
    if visited is None:
        visited = set()

    visited.add(node)
    print(node)  # Process the node — replace with whatever work you need

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

    return visited

DFS with Discovery/Finish Times

def dfs_timestamps(graph):
    """Compute discovery and finish times for all nodes.
    
    These timestamps power edge classification, topological sort,
    and SCC algorithms. The time counter increments globally across
    all DFS trees in the forest.
    """
    visited = set()
    discovery = {}
    finish = {}
    time = [0]  # Mutable container so the nested function can modify it
                # (Python closures can read but not assign to enclosing variables)

    def visit(node):
        time[0] += 1
        discovery[node] = time[0]
        visited.add(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visit(neighbor)

        time[0] += 1
        finish[node] = time[0]

    # Handle disconnected graphs: try starting DFS from every node
    for node in graph:
        if node not in visited:
            visit(node)

    return discovery, finish

Iterative DFS

function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const node = stack.pop();

    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    // Push neighbors in reverse order so we visit them
    // in the same order as recursive DFS (stack is LIFO,
    // so last pushed = first popped)
    const neighbors = graph[node] || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      if (!visited.has(neighbors[i])) {
        stack.push(neighbors[i]);
      }
    }
  }
  return order;
}

Cycle Detection in Directed Graphs (Three-Color)

def has_cycle(graph):
    """Detect cycles in a directed graph using three-state DFS.
    
    WHITE (0) = unvisited
    GRAY (1)  = in-progress (on the current DFS path)
    BLACK (2) = finished (all descendants explored)
    
    A back edge (to a GRAY node) means a cycle exists.
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(u):
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                return True   # Back edge found — cycle!
            if color[v] == WHITE and dfs(v):
                return True
        color[u] = BLACK
        return False

    # Check every node (graph might be disconnected)
    return any(color[node] == WHITE and dfs(node) for node in graph)

DFS on a Grid (Flood Fill)

def count_islands(grid):
    """Count connected components of '1's in a 2D grid.
    
    Classic 'Number of Islands' problem. Each island is a connected
    component of land cells ('1'). DFS from each unvisited '1' marks
    the whole island as visited.
    """
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0

    def flood_fill(r, c):
        # Out of bounds or not land? Stop.
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '#'  # Mark visited by modifying in-place
        # Recurse in all 4 directions
        flood_fill(r + 1, c)
        flood_fill(r - 1, c)
        flood_fill(r, c + 1)
        flood_fill(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                flood_fill(r, c)
                count += 1

    return count

Real-World Example: Web Crawler

Search engines like Google use crawlers to discover web pages. At its core, a web crawler is DFS (or BFS) over the graph of hyperlinks. You start at a seed URL, fetch the page, extract all links, and follow each one — going deeper and deeper until you've found everything reachable.

In practice, crawlers use BFS more often (to prioritize pages close to well-known sites), but the DFS approach works well for focused crawls — say, discovering all pages within a single domain.

import requests
from urllib.parse import urljoin, urlparse
from html.parser import HTMLParser

class LinkExtractor(HTMLParser):
    """Pulls all href links out of an HTML page."""
    def __init__(self):
        super().__init__()
        self.links = []
    
    def handle_starttag(self, tag, attrs):
        if tag == 'a':
            for name, value in attrs:
                if name == 'href':
                    self.links.append(value)

def crawl_domain(start_url, max_pages=100):
    """DFS crawl of a single domain. Discovers all reachable pages.
    
    This mirrors how DFS works on any graph:
    - Nodes = web pages (URLs)
    - Edges = hyperlinks from one page to another
    - visited set = pages we've already fetched
    - Stack = pages to visit next (using the call stack here)
    """
    domain = urlparse(start_url).netloc
    visited = set()
    pages_found = []

    def visit(url):
        if len(visited) >= max_pages:
            return
        if url in visited:
            return

        # Normalize URL and ensure we stay on the same domain
        parsed = urlparse(url)
        if parsed.netloc != domain:
            return

        visited.add(url)
        pages_found.append(url)

        try:
            response = requests.get(url, timeout=5)
            parser = LinkExtractor()
            parser.feed(response.text)

            for link in parser.links:
                # Convert relative URLs to absolute
                absolute = urljoin(url, link)
                visit(absolute)  # DFS: go deep before coming back
        except Exception:
            pass  # Skip pages that fail to load

    visit(start_url)
    return pages_found

# Usage: crawl_domain("https://example.com")

Notice the structure: it's the exact same pattern as basic DFS — visit node, mark visited, recurse on unvisited neighbors. The "graph" is implicit (defined by hyperlinks rather than an adjacency list), but the algorithm is identical.

Interview Patterns

Common DFS Applications

• Flood fill: Mark connected regions (Number of Islands). DFS from each unvisited land cell.
• Path existence: "Can you reach B from A?" DFS is simpler than BFS here — just follow edges.
• Topological sort: Reverse post-order of DFS gives a valid ordering. Used in build systems, course scheduling.
• Tree problems: Most binary tree questions (height, diameter, path sum, serialize/deserialize) are naturally recursive DFS.
• Graph coloring: DFS + backtracking for map coloring, Sudoku, constraint satisfaction.
• Bridges and articulation points: Tarjan's algorithm uses DFS with low-link values to find critical edges/nodes.
• Bipartite check: DFS with two-coloring — alternate colors on each level. If you ever color-conflict, it's not bipartite.

Practice Problems