# DFS tree (algorithm)

Last edited: 2026-01-28

DFS tree

Given a run of a DFS algorithm $A$ on a directed graph $G = (V,E)$, the DFS tree is a subgraph -forest $F = (V,E')$ where $E'$ are the edges used by $A$ to first explore a vertex.

Edges in $G$ can be described in relation to the edges in $F$.

Edges

An edge $e \in E$ can be described as one of the following in relation to $F$:

  • Tree edges: edges $e \in E'$
  • Back edges: edges that connect two nodes in the same branch where the origin node is further away from the root node than the terminus.
  • Forward edges: edges that connect two nodes in the same branch where the origin node is closer to the root node than the terminus.
  • Cross edges: edges that connect two branches.