Chapter 2 · Trees
Depth-First Search
The recursion that classifies every edge, finds cycles, and produces subtrees, low-links and topological order.
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.
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])
};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.
Suppose uv is not a tree edge; WLOG tin(u) < 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:
Four corollaries, one line each
- a cycle exists ⇔ there is a back edge (DFS finds one in O(n+m)),
- ⇔ some edge connects two vertices of the same DFS subtree branch,
- the graph is bipartite ⇔ no back edge has even "depth parity" difference (Bipartite Graphs and 2-Colouring uses BFS, DFS works too),
- bridges: uv (tree edge, u parent of v) is a bridge ⇔ low[v] > tin[u] where low is the smallest tin reachable from v's subtree using at most one back edge (Connectivity, Bridges, Articulation Points).
#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).
A digraph has a cycle ⇔ DFS finds a back edge.
Back edge u → v with v grey: v is an ancestor of u in the DFS tree, so v ⇝ u (tree edges) plus u → 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 = 106)
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.
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.
The push steps are the grey stack; the back edge steps are exactly the ones the cycle lemma talks about.