---
title: Depth-First Search
summary: The recursion that classifies every edge, finds cycles, and produces subtrees, low-links and topological order.
difficulty: core
tags: [traversal, recursion, cycles]
time: n + m
space: n
prereq: [foundations/representation]
see: [trees/euler-tour, directed/dag-toposort, foundations/connectivity]
---

DFS is not "BFS with a stack" — that description hides the useful part. DFS explores one branch to the end and *finishes* vertices in reverse order of discovery, and it is the **finish order** that carries information.

```cpp dfs.cpp
vector<int> vis(n), tin(n), tout(n), par(n, -1);
int timer = 0;
function<void(int)> dfs = [&](int u) {
    vis[u] = 1; tin[u] = timer++;
    for (int v : g[u]) {
        if (par[u] == v) continue;         // ignore the tree edge we came from
        if (vis[v]) { /* back edge: u–v closes a cycle */ }
        else { par[v] = u; dfs(v); }
    }
    tout[u] = timer;                        // subtree of u = [tin[u], tout[u])
};
```

:::theorem title="Edge classification (undirected, DFS forest)"
Every edge of an undirected graph, run through DFS, is exactly one of:
- **tree edge** — it discovered a new vertex,
- **back edge** — it joined $u$ to an ancestor $v$ already on the stack.
There are *no* cross edges: if $uv$ joined two unrelated branches, whichever one was explored first would have discovered the other.
:::

:::proof
Suppose $uv$ is not a tree edge; WLOG $\operatorname{tin}(u) < \operatorname{tin}(v)$. When $u$ was on the stack and scanned $uv$, either $v$ was already visited — meaning $v$ is an ancestor, because a visited-and-finished $v$ would have needed $u$ visited to be finished — or $v$ was unvisited and $uv$ became a tree edge. Contradiction, so $v$ is an ancestor: back edge. ∎
:::

That single lemma gives:

:::props title="Four corollaries, one line each"
- a cycle exists $\iff$ there is a back edge (DFS finds one in $O(n+m)$),
- $\iff$ some edge connects two vertices of the same DFS subtree branch,
- the graph is bipartite $\iff$ no back edge has even "depth parity" difference (@foundations/bipartite uses BFS, DFS works too),
- **bridges**: $uv$ (tree edge, $u$ parent of $v$) is a bridge $\iff$ $\operatorname{low}[v] > \operatorname{tin}[u]$ where $\operatorname{low}$ is the smallest $\operatorname{tin}$ reachable from $v$'s subtree using at most one back edge (@foundations/connectivity).
:::

## Directed graphs add a third type
With three colours (white/grey/black) a directed DFS edge is **tree**, **back** (to a grey vertex — the *only* kind that means a cycle), **forward** (to a black descendant) or **cross** (to a black vertex in an earlier branch).

:::theorem title="Cycle test"
A digraph has a cycle $\iff$ DFS finds a back edge.
:::

:::proof
Back edge $u \to v$ with $v$ grey: $v$ is an ancestor of $u$ in the DFS tree, so $v \leadsto u$ (tree edges) plus $u \to v$ is a cycle. Conversely, take the cycle $C$ and let $w$ be the first vertex of $C$ to be discovered; DFS follows $C$ from $w$ (all its successors on $C$ are white when scanned) and so returns to $w$ by a back edge. ∎
:::

## Iterative DFS (when $n = 10^6$)
```cpp dfs-iterative.cpp
vector<int> st{ s }, it(n);              // it[u] = next child index to try
par[s] = -1; tin[s] = 0;
while (!st.empty()) {
    int u = st.back();
    if (it[u] < (int)g[u].size()) {
        int v = g[u][it[u]++];
        if (v == par[u]) continue;
        if (vis[v]) { /* back edge */ }
        else { vis[v] = 1; par[v] = u; tin[v] = timer++; st.push_back(v); }
    } else { tout[u] = timer; st.pop_back(); }   // finish
}
```
This is the version to write when the recursion depth could be $n$ (a path graph is a legal test case), because a stack overflow is not a wrong answer you can debug — it is a runtime error at 0.4 s that looks like a bug in your code.

:::trap title="DFS order is not distance order"
`tin` tells you *nothing* about shortest paths. Two uses that are frequently confused: subtree interval (fine with DFS) versus level/layer (needs BFS). "Shortest path in an unweighted graph with DFS" is a wrong algorithm, not a slow one.
:::

:::demo id="traversal" caption="The `push` steps are the grey stack; the `back edge` steps are exactly the ones the cycle lemma talks about."
:::

:::problems
- [[CSES 1669]] Round Trip | https://cses.fi/problemset/task/1669 | core | undirected cycle
- [[CF 977E]] Cyclic Components | https://codeforces.com/problemset/problem/977/E | core | DFS classification
- [[CSES 1679]] Course Schedule | https://cses.fi/problemset/task/1679 | core | DFS + cycle
- [[CF 459E]] Pashmak and Graph | https://codeforces.com/problemset/problem/459/E | hard | edge orientation
:::