Difference between edges in Depth First Trees

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

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.

Answer 1

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.

Answer 2

wikipedia has the good explaination about this.

A convenient description of a depth first search of a graph is in terms of a spanning tree of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

The four types of edges defined by a spanning tree

In my opinion we use back & forward ages to make a fully spanning tree. In your graph N P M are Isolated nodes so to traverse these nodes we have to put back or forward ages (not sure about this).

See this answer you will get a clear picture.