Depth-First Search

The problem

You're standing in a hedge maze. There's no map, just corridors and junctions. How do you guarantee you visit every dead end without wandering forever? The natural human strategy: pick a corridor and follow it as far as it goes. Hit a dead end, back up to the last junction, and take the next unexplored corridor. Repeat until nothing new is left.

That's exploring a graph where junctions are vertices and corridors are edges. The strategy has to remember where to back up to, and it has to avoid re-treading corridors it has already walked, or it loops forever in a maze with cycles. That "go deep, then back up" instinct is depth-first search.

A first attempt

You could try to be systematic without backtracking — say, always turn left. In a simply connected maze that famously works, but general graphs aren't mazes with walls; a vertex can link to any others, and "left" is meaningless. Worse, without tracking where you've been, any cycle sends you round and round the same corridors, never terminating.

So two things are non-negotiable: a way to remember the path back to earlier junctions, and a visited set so each vertex is entered once.

The insight

"Back up to the last junction" is exactly last in, first out — the most recently entered vertex is the first you return to. That's a stack. Recursion gives you one for free (the call stack), or you can carry an explicit stack.

Combine the stack with a visited set and the method is complete: dive down an edge to an unvisited neighbor, recurse, and when a vertex has no unvisited neighbors left, return — which pops you back to where you came from. Every vertex entered once, every edge examined once.

How it works

DFS from 0, always taking the lowest-numbered unvisited neighbor, visits 0 → 1 → 3 → 2 → 4, backing up each time a branch dead-ends:

      (1)---(3)
     /
   (0)
     \
      (2)---(4)

dive 0→1→3   (3 dead-ends) back to 1, back to 0
dive 0→2→4   (4 dead-ends) back to 2, back to 0
order visited: 0, 1, 3, 2, 4

The code

def dfs(adj, start):
    visited = [False] * len(adj)
    order = []

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

    visit(start)
    return order

# Iterative version with an explicit stack:
def dfs_iter(adj, start):
    visited = [False] * len(adj)
    stack, order = [start], []
    while stack:
        u = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)
        for v in reversed(adj[u]):   # reversed -> visit lowest first
            if not visited[v]:
                stack.append(v)
    return order

function dfs(adj: number[][], start: number): number[] {
  const visited = new Array(adj.length).fill(false);
  const order: number[] = [];

  function visit(u: number): void {
    visited[u] = true;
    order.push(u);
    for (const v of adj[u]) {
      if (!visited[v]) visit(v);
    }
  }

  visit(start);
  return order;
}

import java.util.*;

List<Integer> dfs(List<List<Integer>> adj, int start) {
    boolean[] visited = new boolean[adj.size()];
    List<Integer> order = new ArrayList<>();
    visit(adj, start, visited, order);
    return order;
}

void visit(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {
    visited[u] = true;
    order.add(u);
    for (int v : adj.get(u)) {
        if (!visited[v]) visit(adj, v, visited, order);
    }
}

#include <stdbool.h>

bool visited[100000];

void dfs(int adj[][100], int deg[], int u) {
    visited[u] = true;
    /* process u here */
    for (int i = 0; i < deg[u]; i++) {
        int v = adj[u][i];
        if (!visited[v]) dfs(adj, deg, v);
    }
}

#include <vector>

void dfs(const std::vector<std::vector<int>>& adj, int u,
         std::vector<bool>& visited, std::vector<int>& order) {
    visited[u] = true;
    order.push_back(u);
    for (int v : adj[u]) {
        if (!visited[v]) dfs(adj, v, visited, order);
    }
}

Complexity

Same asymptotics as BFS — both are linear in the graph's size. The difference is order of visitation, not cost.

When to use it

Practice

Recap

• DFS explores as deep as possible, then backtracks, using a stack (often the call stack via recursion).
• It runs in O(n + m) time and O(n) space — same as BFS, but a different visiting order.
• It's the foundation for cycle detection, topological sort, and connectivity — but it does not find shortest paths.