Question

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A).

The result is $M,N,P,O,Q,S,R,T$ (after reversing). Several DFS trees are created during this traversal, and it's the edges between the trees that confuse me. I understand how tree, back, forward and cross edges work in simpler graphs - but this one's harder.

For the example, with the graph The graph

We have the next depth-first trees:

  1. $T$
  2. $S\rightarrow R$
  3. $Q$
  4. $P\rightarrow O$
  5. $M$
  6. $N$

And my question is regarding the edges that connect the trees.

Which are cross edges (like $O,R$), which are back edges and which are forward edges? And giving an example of when they are assigned as back edges / cross edges would be awesome.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top