A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
DFS explores a graph deeply via recursion or an explicit stack, visiting unvisited neighbors. It finds connected components, detects cycles, computes finish times (for topological sort), and identifies strongly connected components.
From your study of graph representations (adjacency lists and matrices) and the basic DFS traversal, you know that DFS explores a graph by going as deep as possible along each branch before backtracking. Now we focus on what DFS *produces* beyond mere traversal — the structural information it reveals about a graph, and how that information powers important algorithms.
The key to understanding DFS applications is the concept of discovery and finish times. As DFS runs, it timestamps each node twice: once when the node is first discovered (pushed onto the call stack), and once when it is finished (all descendants have been fully explored and the call returns). These timestamps encode the recursive structure of the search. If node A has a smaller discovery time and larger finish time than node B, then B was explored entirely within A's recursive call — meaning B is a descendant of A in the DFS tree. This parenthetical nesting of intervals is what makes finish times so powerful.
Cycle detection falls out naturally from DFS. During traversal, if you encounter an edge leading to a node that has been discovered but not yet finished — meaning it's still on the call stack, an ancestor in the current path — you've found a back edge, which proves a cycle exists. In an undirected graph, any edge to an already-visited node (other than the parent) indicates a cycle. In a directed graph, only back edges indicate cycles; edges to fully finished nodes (cross edges or forward edges) do not. This distinction matters for applications like determining whether a directed graph is a DAG (directed acyclic graph): run DFS, and if no back edges appear, the graph has no cycles.
Topological sorting uses finish times directly. For a DAG, if you output nodes in reverse order of their finish times, the result is a valid topological ordering — every node appears before all nodes it has edges to. This works because in a DAG (no back edges), if there is an edge from A to B, then A will always finish after B in a DFS. Topological sort is essential for dependency resolution: build systems, course prerequisite planning, and task scheduling all reduce to this operation. Connected components in an undirected graph are found by running DFS from each unvisited node — each DFS call discovers exactly one component. For directed graphs, finding strongly connected components (maximal sets of nodes where every node can reach every other) uses two DFS passes: one on the original graph to compute finish times, and one on the transposed graph processing nodes in reverse finish-time order. Each DFS call in the second pass reveals one strongly connected component.