4
$\begingroup$

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?

$\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$ Commented Sep 7, 2013 at 13:21

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.