Depth-first search

Explore a graph like a maze: keep going forward along unvisited paths; at a dead end, back up to the last place with an unexplored turning and try it.

Time	Extra space	Finds
\(O(V + E)\)	\(O(V)\) (the stack)	reachability, components, cycles, and the order used by many other algorithms

The idea

Exploring a maze with a ball of string, you follow one corridor as far as it goes. When everything ahead is explored, you wind the string back to the last junction with an untried corridor. That is depth-first search. The string is a stack: recursion keeps it for you (the call stack), or you keep one yourself.

DFS does not find shortest paths, but the shape of its search carries a lot of information. It visits each vertex once and walks each edge once or twice, and the times at which vertices are entered and finished reveal cycles, give topological orders, and find strongly connected components, bridges and articulation points.

How it works

visit(u): mark u seen; for each neighbour v of u, if v is not seen, visit(v).

To cover a whole graph, call visit on each vertex not yet seen; each call explores one connected component.

Code

Four uses: the recursive order, the same order with an explicit stack, labelling connected components, and detecting a cycle in an undirected graph.

PythonJavaC++

def dfs_order(adj, start):
    """The order in which depth-first search first visits the vertices reachable from start."""
    seen = [False] * len(adj)
    order = []

    def visit(u):
        seen[u] = True
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                visit(v)                     # go as deep as possible before trying u's next neighbour
    visit(start)
    return order


def dfs_iterative(adj, start):
    """The same order without recursion, using an explicit stack (safe for huge graphs)."""
    seen = [False] * len(adj)
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if seen[u]:
            continue
        seen[u] = True
        order.append(u)
        for v in reversed(adj[u]):           # reversed, so the first neighbour is popped first
            if not seen[v]:
                stack.append(v)
    return order


def components(adj):
    """Labels each vertex with the number of its connected component."""
    comp = [-1] * len(adj)
    count = 0
    for s in range(len(adj)):
        if comp[s] == -1:                    # a new component starts here
            stack = [s]
            comp[s] = count
            while stack:
                u = stack.pop()
                for v in adj[u]:
                    if comp[v] == -1:
                        comp[v] = count
                        stack.append(v)
            count += 1
    return count, comp


def has_cycle(adj):
    """Undirected graph: is there a cycle? (An edge to an already-seen vertex other than our parent.)"""
    seen = [False] * len(adj)
    for s in range(len(adj)):
        if seen[s]:
            continue
        stack = [(s, -1)]
        seen[s] = True
        while stack:
            u, parent = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append((v, u))
                elif v != parent:
                    return True
    return False


def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj


if __name__ == "__main__":
    adj = build(8, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 5), (6, 7)])
    print(dfs_order(adj, 0), dfs_iterative(adj, 0))
    print(components(adj))
    tree = build(5, [(0, 1), (0, 2), (2, 3), (2, 4)])
    print(has_cycle(adj), has_cycle(tree))

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Dfs {
    static List<List<Integer>> adj;
    static boolean[] seen;
    static List<Integer> order;

    /** The order in which depth-first search first visits the vertices reachable from start. */
    static List<Integer> dfsOrder(List<List<Integer>> g, int start) {
        adj = g; seen = new boolean[g.size()]; order = new ArrayList<>();
        visit(start);
        return order;
    }

    static void visit(int u) {
        seen[u] = true;
        order.add(u);
        for (int v : adj.get(u))
            if (!seen[v]) visit(v);                   // go as deep as possible before u's next neighbour
    }

    /** The same order without recursion, using an explicit stack (safe for huge graphs). */
    static List<Integer> dfsIterative(List<List<Integer>> g, int start) {
        boolean[] seen = new boolean[g.size()];
        List<Integer> order = new ArrayList<>();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (seen[u]) continue;
            seen[u] = true;
            order.add(u);
            List<Integer> nb = g.get(u);
            for (int i = nb.size() - 1; i >= 0; i--)  // reversed, so the first neighbour is popped first
                if (!seen[nb.get(i)]) stack.push(nb.get(i));
        }
        return order;
    }

    /** Labels each vertex with the number of its connected component; returns the count. */
    static int components(List<List<Integer>> g, int[] comp) {
        Arrays.fill(comp, -1);
        int count = 0;
        for (int s = 0; s < g.size(); s++) {
            if (comp[s] != -1) continue;              // already labelled
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            stack.push(s);
            comp[s] = count;
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : g.get(u))
                    if (comp[v] == -1) { comp[v] = count; stack.push(v); }
            }
            count++;
        }
        return count;
    }

    /** Undirected graph: is there a cycle? (An edge to an already-seen vertex other than our parent.) */
    static boolean hasCycle(List<List<Integer>> g) {
        boolean[] seen = new boolean[g.size()];
        for (int s = 0; s < g.size(); s++) {
            if (seen[s]) continue;
            ArrayDeque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{s, -1});
            seen[s] = true;
            while (!stack.isEmpty()) {
                int[] top = stack.pop();
                int u = top[0], parent = top[1];
                for (int v : g.get(u)) {
                    if (!seen[v]) { seen[v] = true; stack.push(new int[]{v, u}); }
                    else if (v != parent) return true;
                }
            }
        }
        return false;
    }

    static List<List<Integer>> build(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        return g;
    }

    static String py(boolean b) { return b ? "True" : "False"; }

    public static void main(String[] args) {
        List<List<Integer>> g = build(8, new int[][]{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5}, {6, 7}});
        System.out.println(dfsOrder(g, 0) + " " + dfsIterative(g, 0));
        int[] comp = new int[8];
        int count = components(g, comp);
        System.out.println("(" + count + ", " + Arrays.toString(comp) + ")");
        List<List<Integer>> tree = build(5, new int[][]{{0, 1}, {0, 2}, {2, 3}, {2, 4}});
        System.out.println(py(hasCycle(g)) + " " + py(hasCycle(tree)));
    }
}

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

using Graph = vector<vector<int>>;

void visit(const Graph& adj, int u, vector<bool>& seen, vector<int>& order) {
    seen[u] = true;
    order.push_back(u);
    for (int v : adj[u])
        if (!seen[v]) visit(adj, v, seen, order);   // go as deep as possible before u's next neighbour
}

// The order in which depth-first search first visits the vertices reachable from start.
vector<int> dfsOrder(const Graph& adj, int start) {
    vector<bool> seen(adj.size(), false);
    vector<int> order;
    visit(adj, start, seen, order);
    return order;
}

// The same order without recursion, using an explicit stack (safe for huge graphs).
vector<int> dfsIterative(const Graph& adj, int start) {
    vector<bool> seen(adj.size(), false);
    vector<int> order, stack = {start};
    while (!stack.empty()) {
        int u = stack.back(); stack.pop_back();
        if (seen[u]) continue;
        seen[u] = true;
        order.push_back(u);
        for (int i = (int)adj[u].size() - 1; i >= 0; i--)   // reversed, so the first neighbour is popped first
            if (!seen[adj[u][i]]) stack.push_back(adj[u][i]);
    }
    return order;
}

// Labels each vertex with the number of its connected component; returns the count.
int components(const Graph& adj, vector<int>& comp) {
    comp.assign(adj.size(), -1);
    int count = 0;
    for (int s = 0; s < (int)adj.size(); s++) {
        if (comp[s] != -1) continue;                 // already labelled
        vector<int> stack = {s};
        comp[s] = count;
        while (!stack.empty()) {
            int u = stack.back(); stack.pop_back();
            for (int v : adj[u])
                if (comp[v] == -1) { comp[v] = count; stack.push_back(v); }
        }
        count++;
    }
    return count;
}

// Undirected graph: is there a cycle? (An edge to an already-seen vertex other than our parent.)
bool hasCycle(const Graph& adj) {
    vector<bool> seen(adj.size(), false);
    for (int s = 0; s < (int)adj.size(); s++) {
        if (seen[s]) continue;
        vector<pair<int, int>> stack = {{s, -1}};
        seen[s] = true;
        while (!stack.empty()) {
            auto [u, parent] = stack.back(); stack.pop_back();
            for (int v : adj[u]) {
                if (!seen[v]) { seen[v] = true; stack.push_back({v, u}); }
                else if (v != parent) return true;
            }
        }
    }
    return false;
}

Graph build(int n, const vector<pair<int, int>>& edges) {
    Graph adj(n);
    for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
    return adj;
}

void print(const vector<int>& a) {
    cout << "[";
    for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
    cout << "]";
}

int main() {
    Graph g = build(8, {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {2, 5}, {6, 7}});
    print(dfsOrder(g, 0)); cout << " "; print(dfsIterative(g, 0)); cout << "\n";
    vector<int> comp;
    int count = components(g, comp);
    cout << "(" << count << ", "; print(comp); cout << ")\n";
    Graph tree = build(5, {{0, 1}, {0, 2}, {2, 3}, {2, 4}});
    cout << (hasCycle(g) ? "True" : "False") << " " << (hasCycle(tree) ? "True" : "False") << "\n";
}

Output: the visiting order [0, 1, 3, 2, 5, 4] both ways; 2 components; True (the graph has the cycle 0–1–3–2–0) and False for a tree.

When to use it

• Is \(t\) reachable from \(s\)? How many connected parts? (Either BFS or DFS works.)
• Cycles: in an undirected graph, an edge to a seen vertex that is not your parent; in a directed graph, an edge back into the current path.
• Topological sort, strongly connected components, bridges and articulation points (Tarjan's low-link values).
• Exploring all possibilities with backtracking: DFS over a tree of choices.
• Maze generation (randomized DFS makes long winding corridors).

Common mistakes

• Recursion depth: a path-shaped graph with \(10^5\) vertices overflows the default stack in Python and often in Java. Use the iterative version or raise the limit.
• Forgetting the parent check when looking for cycles in an undirected graph: the edge back to your parent is not a cycle.
• Marking too late in the iterative version, so vertices are pushed many times (harmless for correctness here, because of the if seen: continue, but it costs memory).
• Expecting shortest paths: DFS paths can be very long.

Going deeper

Each part below starts closed; open the ones you want.

Sample walkthrough: DFS from 0

Neighbour lists: 0: 1, 2 · 1: 0, 3 · 2: 0, 3, 5 · 3: 1, 2, 4 · 4: 3, 5 · 5: 4, 2.

visit 0
  visit 1            (0's first neighbour)
    visit 3          (1's next unseen neighbour)
      visit 2        (3's first unseen neighbour)
        visit 5      (2's next unseen neighbour)
          visit 4    (5's first neighbour)
          4 done: all its neighbours are seen
        5 done, 2 done, back in 3: 4 is seen, 3 done
    1 done
  0 done: 2 is already seen

Order of first visits: 0, 1, 3, 2, 5, 4.

The math: edge types and the parenthesis theorem

Record for each vertex the time it is entered, \(d[v]\), and finished, \(f[v]\), using one clock that ticks at each event.

Parenthesis theorem. For any two vertices \(u, v\), the intervals \([d[u], f[u]]\) and \([d[v], f[v]]\) are either disjoint or one contains the other; and \(v\) is a descendant of \(u\) in the DFS forest exactly when \([d[v], f[v]] \subset [d[u], f[u]]\). (Writing "(u" at entry and "u)" at finish gives balanced brackets.)

Edge types in a directed graph, for an edge \(u \to v\) met while exploring \(u\):

When \(v\) is ...	Edge type
unseen	tree edge
entered but not finished (on the current path)	back edge: closes a cycle
finished, and \(d[u] < d[v]\)	forward edge
finished, and \(d[v] < d[u]\)	cross edge

A directed graph has a cycle if and only if DFS finds a back edge. In an undirected graph only tree and back edges exist.

White-path theorem. \(v\) becomes a descendant of \(u\) exactly when, at time \(d[u]\), there is a path from \(u\) to \(v\) through unvisited vertices only.

Time. Each vertex is visited once and each adjacency list scanned once: \(O(V + E)\).

Watch it step by step

Blue vertices are on the call stack (orange: the current one); green ones are finished.

Variations and related ideas

• Bridges and articulation points (Hopcroft and Tarjan): with \(\text{low}[v]\), the earliest entry time reachable by one back edge from \(v\)'s subtree, an edge \(u\)–\(v\) is a bridge when \(\text{low}[v] > d[u]\).
• Iterative deepening DFS: DFS with a depth limit of 1, 2, 3, ...: finds shortest paths with DFS's small memory; used in puzzle solvers (IDA*).
• Euler tours (Hierholzer's algorithm) walk every edge exactly once.
• Tree traversals (pre-order, in-order, post-order) are DFS on a tree.

See also

• Breadth-first search
• Topological sort and strongly connected components: built on DFS
• Recursion and backtracking

References

• R. E. Tarjan, "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1(2), 1972.
• T. H. Cormen et al., Introduction to Algorithms, 4th ed., §20.3 (depth-first search).