A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Depth-first search (DFS) explores a graph by going as deep as possible along each branch before backtracking. It can be implemented recursively or iteratively with an explicit stack, and runs in O(V + E) time. DFS is the foundation for cycle detection, topological sorting, strongly connected components (Tarjan's and Kosaraju's algorithms), and solving maze-like problems. Tracking discovery and finish times during DFS produces edge classifications: tree edges, back edges (cycles), forward edges, and cross edges.
Implement recursive DFS tracking discovery and finish timestamps. Then implement the iterative stack version and verify equivalent results. Use DFS to detect cycles in both directed and undirected graphs as a practical exercise.
If you have written recursive tree traversals (like inorder or postorder), you have already implemented a special case of depth-first search — trees are acyclic graphs, and DFS on a tree is exactly what those traversals do. Generalizing to arbitrary graphs requires only one addition: a visited set to avoid processing the same node twice (and to prevent infinite loops in cyclic graphs).
The DFS algorithm works like this: start at a source node, mark it visited, then recursively visit each unvisited neighbor before returning. The "depth-first" name captures the behavior — you commit fully to one branch, following it to its dead end, before backtracking and trying another. The call stack (or an explicit stack data structure if implemented iteratively) holds the current path from the source to wherever you are. This is fundamentally different from BFS, which explores level by level. Neither is universally better — they answer different questions.
DFS has a remarkable side effect: the order in which nodes are *entered* (discovery time) and *exited* (finish time) produces a classification of every edge in the graph. A tree edge is one you traverse to an unvisited node. A back edge points from a node to an ancestor currently on the stack — finding one proves a cycle exists in the directed graph. Forward and cross edges cover other cases. This edge classification is the foundation for algorithms like topological sort (process nodes in reverse finish-time order) and strongly connected components (Tarjan's algorithm uses discovery and finish times directly).
Cycle detection deserves special care. In an undirected graph, any edge to an already-visited node that isn't your direct parent means a cycle exists (you reached the same node via two different paths). In a directed graph, the rule is stricter: only a back edge — one that points to a node still on the active recursion stack — proves a cycle. A directed edge to a node that was visited in a previous DFS branch (a cross edge) doesn't create a cycle, because that edge goes from one branch to another, not backward along the current path.
The O(V + E) time complexity follows naturally from the algorithm's structure: each vertex is visited exactly once, and each edge is examined exactly once when its source vertex is being processed. This makes DFS efficient even on large sparse graphs, and it's why DFS is the go-to building block for so many graph algorithms.