A depth-first traversal of any graph induces a labeling of every edge into exactly four categories: tree (forms the DFS spanning tree, the connectivity skeleton), back (returns to an ancestor of the current node, creating a cycle), forward (jumps to a non-child descendant, a tree-path shortcut), and cross (links separate subtrees of the same DFS forest, lateral relationships). The classification falls out of the search itself; you don’t run a second pass.
This is not a curiosity of bookkeeping. The labels expose graph structure. Back edges directly witness cycles, so cycle detection in directed graphs reduces to “find a back edge during DFS” with no extra machinery. Topological ordering emerges from DFS finishing times: in a DAG, sorting nodes by descending finish time produces a valid linearization. Strongly connected components fall out of two DFS passes (Kosaraju) or a single pass with low-link tracking (Tarjan). Bridges and Articulation Points use the back-edge timing to find vertices and edges whose removal disconnects the graph.
The deeper point is that DFS is not just a search procedure; it is structure analysis. The act of running it decomposes the graph into a spanning tree plus a precise account of the non-tree connections. Many graph problems, especially those about connectivity properties, reduce to “label the edges with DFS, then read the answer off the labels” rather than “design a custom cycle-finder.” BFS produces a similar structural summary but with different labels (tree and cross only, no back or forward) because it visits in distance order rather than finishing order. See DFS and BFS Are Complementary Search Strategies for the broader dichotomy.