DFS tree
Given the run a DFS algorithm
on a directed graph , the DFS tree is a sub-forest where are the edges used by to first explore a vertex.
Edges in
Edges
An edge
can be described as one of the following in relation to :
- Tree edges: edges
- 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.