Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms (resit) / 7 / b / Solution

Relative to the resulting DFS edge classification, a tree edge in depth-first search discovers a white vertex and becomes its parent edge. A forward edge in depth-first search goes to a proper descendant but is not that descendant's discovery edge. A back edge in depth-first search goes to an active ancestor, with a self-loop also counted as a back edge when such edges are allowed. A cross edge in depth-first search joins vertices with no ancestor-descendant relationship in the forest, such as different completed branches or different trees.

The definitions refer to directed edges; an undirected graph is normally classified only with tree and back edges, accounting for the reverse copy of a parent edge separately.