Plunging deep before backtracking
Depth-first search drives down one branch as far as possible, then backtracks and explores other branches. A stack drives the traversal: when you visit a node, push its unvisited neighbors onto the stack. When you run out of neighbors, pop and continue from the last branching point. This produces a DFS tree with edges classified as tree edges, back edges (to ancestors, revealing cycles), forward edges, and cross edges. The structure of these edges reveals the connectivity and dependency structure of the graph.
Strong connectivity and topological order
DFS is essential for finding strongly connected components (maximal subsets where every node can reach every other). A two-pass DFS algorithm (once on the original graph, once on the transpose) partitions the graph into SCCs. DFS also computes a topological order for directed acyclic graphs (visiting nodes in reverse finish order). These subroutines are building blocks for more complex graph algorithms, from network flow to reachability analysis.