Difference between edges in Depth First Trees

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

We have the next depth-first trees:

• $T$

• $S\rightarrow R$

• $Q$

• $P\rightarrow O$

• $M$

• $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.

You could find a nicely description in CLRS 3ed Chapter 22.3. I extracted the next description from there. There are just four types of edge in a graph.

• Tree edges are edges in the depth-first forest $G_\pi$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.

• Back Edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges.

• Forward Edges: are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.

• Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or the can go between vertices in different depth-first trees.

For that, because you're interested in depth-first forest ( graph contains all depth-first search trees) only two types of edges remain:

• Tree Edges: edges with a first node without parents in the forest of depth first search trees $G_\pi$

• Cross Edges: edges inside depth-first trees with the description above, and those edges connecting those dfs-trees.

StackExchange Computer Science Q#33998, answer score: 4