Beyond basic DFS traversal, advanced DFS patterns solve graph structure problems: finding cycles, identifying critical nodes and edges, and decomposing graphs into strongly connected components. These appear in senior coding interviews and competitive programming. This guide covers the patterns with clear algorithms and their interview applications.
Cycle Detection in Directed Graphs
Three-state DFS: mark nodes as WHITE (unvisited), GRAY (visiting — in the current DFS path), and BLACK (visited — fully processed). Start DFS from each WHITE node. On entering a node: mark GRAY. Explore all neighbors: if a neighbor is WHITE, recurse. If a neighbor is GRAY (in the current path), a cycle exists — this is a back edge. If BLACK, already processed (no cycle through this neighbor). On finishing a node (all neighbors processed): mark BLACK. Time: O(V + E). Why three states: two states (visited/unvisited) are insufficient for directed graphs. A node marked “visited” might be reachable via a different path without forming a cycle. The GRAY state specifically tracks nodes in the current recursion stack — a back edge to a GRAY node means we have found a path from that node back to itself. Applications: Course Schedule (can all courses be taken? = no cycle in prerequisite graph), Detect Cycle in a Directed Graph, and topological sort (topological order exists if and only if no cycle).
Cycle Detection in Undirected Graphs
Simpler than directed: DFS with parent tracking. When exploring node u neighbors: if a neighbor v is visited AND v is not the parent of u, a cycle exists (we reached an already-visited node via a different path). Why parent matters: in an undirected graph, every edge (u, v) appears twice (u -> v and v -> u). Without parent tracking, going from u to v and back to u would be falsely detected as a cycle. The parent parameter prevents this by skipping the edge back to the node we came from. Union-Find alternative: process edges one by one. If find(u) == find(v) before union(u, v), adding this edge creates a cycle. Time: O(E * alpha(V)) ~= O(E). This is often simpler to implement than DFS for undirected cycle detection. Applications: Redundant Connection (find the extra edge that creates a cycle), Graph Valid Tree (N nodes, N-1 edges, no cycle = tree), and detecting cycles in resource dependency graphs.
Strongly Connected Components (Tarjan/Kosaraju)
A Strongly Connected Component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex (in a directed graph). Kosaraju algorithm (simpler to understand): (1) DFS on the original graph, recording finish times (push to stack on post-order). (2) Transpose the graph (reverse all edges). (3) DFS on the transposed graph in reverse finish-time order (pop from stack). Each DFS tree in step 3 is an SCC. Time: O(V + E). Tarjan algorithm (single DFS pass): maintain a stack of nodes in the current DFS path. Track disc[v] (discovery time) and low[v] (lowest discovery time reachable from v subtree). When low[v] == disc[v], all nodes on the stack above v form an SCC. Time: O(V + E). Applications: (1) Finding redundant connections in a network. (2) 2-SAT (boolean satisfiability with 2 variables per clause) — solvable by finding SCCs in the implication graph. (3) Detecting deadlocks in resource allocation graphs. (4) Simplifying a directed graph into its SCC DAG for further analysis.
Articulation Points and Bridges
An articulation point (cut vertex) is a vertex whose removal disconnects the graph. A bridge (cut edge) is an edge whose removal disconnects the graph. Both identify critical elements in a network. Algorithm (based on Tarjan DFS): track disc[v] and low[v]. low[v] = min(disc[v], disc[w] for back edges, low[child] for tree edges). Articulation point: vertex u is an articulation point if: (1) u is the root of the DFS tree and has 2+ children, OR (2) u is not the root and has a child v where low[v] >= disc[u] (v subtree cannot reach anything above u — removing u disconnects v subtree). Bridge: edge (u, v) is a bridge if low[v] > disc[u] (v subtree has no back edge to u or above — removing (u, v) disconnects v subtree). Time: O(V + E). Applications: (1) Critical Connections in a Network (LeetCode 1192) — find all bridges. Direct application of the algorithm. (2) Network reliability — identify single points of failure. (3) Biconnected components — the graph decomposed by articulation points. Each biconnected component remains connected after any single vertex removal.
DFS on Trees: Euler Tour and LCA
DFS on trees produces useful orderings: Euler Tour: record the node on both entering and leaving during DFS. The result is a sequence of 2N entries. The subtree of node v corresponds to a contiguous range in the Euler tour [enter_time[v], leave_time[v]]. This converts subtree queries into range queries, solvable with segment trees or Fenwick trees. Application: subtree sum queries, subtree updates, and tree flattening for binary indexed tree operations. Lowest Common Ancestor (LCA): the deepest node that is an ancestor of both u and v. Binary lifting approach: precompute up[v][k] = the 2^k-th ancestor of v. To find LCA(u, v): lift u and v to the same depth. Then lift both simultaneously using binary lifting until they meet. Time: O(log N) per query, O(N log N) preprocessing. Euler Tour + RMQ approach: record depths during the Euler tour. LCA(u, v) corresponds to the minimum depth in the range [first_occurrence[u], first_occurrence[v]]. Use a sparse table for O(1) range minimum queries after O(N log N) preprocessing. LCA is used in: distance between two nodes in a tree (dist(u,v) = depth[u] + depth[v] – 2*depth[LCA(u,v)]), path queries, and tree DP optimizations.