# 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:

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.

• Use the definition given in class? – Raphael Dec 8 '14 at 11:59

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:

1. Tree Edges: edges with a first node without parents in the forest of depth first search trees $$G_\pi$$
2. Cross Edges: edges inside depth-first trees with the description above, and those edges connecting those dfs-trees.