[Solved]: Difference between edges in Depth First Trees

Problem Detail: 

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.

Asked By : Jonas Foyn Therkelsen

Answered By : jonaprieto

You could find a nicely description in CLRS 3ed Chapter 22.3. I extracted the next description from there. There are just the four types of 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) you have just two types of edges:

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33998

3.2K people like this

 Download Related Notes/Documents