= Solution
Relative to the resulting <DFS edge classification>, a \b[<tree edge in depth-first search>] discovers a white vertex and becomes its parent edge. A \b[<forward edge in depth-first search>] goes to a proper descendant but is not that descendant's discovery edge. A \b[<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 \b[<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.
Back to article page
