As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are created?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ You need to distinguish between the edges in the DFS-tree and the edges in the original graph, which are then partitioned with respect to the edges in the DFS-tree $\endgroup$– Cornelius BrandSep 7, 2013 at 13:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The terms forward, back and cross edges classify edges in the original graph with respect to the depth-first search, so they don't appear in the DFS tree itself. Different DFS runs may yield different classifications. They are useful in some algorithmic contexts.
You can read more on Wikipedia.