What is the difference between `Cross edge` and `Forward edge` in a DFS tree?

Question

In the most general way,

Let $G(V, E)$ be a graph, and $T(V', E')$ be the DFS tree of $G$.

If an edge $(u, v) \in E'$ is neither a tree edge nor a back edge,

How can we determine whether it's a forward edge or a back edge?

Thanks in advance.

Answer 1

Forward edges point from a vertex to one of its descendants in the tree. Back edges point from a vertex to one of its ancestors in the tree. Cross edges point from one vertex to another vertex to which it is incomparable with respect to the ordering induced by the DFS tree.

That is, $(u,v) \in E'$ is a forward edge if $u$ is an ancestor of $v$, and a back edge if the opposite is true. It is a cross edge if neither $u$ nor $v$ is an ancestor of the other.

In an undirected graph, forward and back edges are indistinguishable.

Answer 2

Wikipedia has the answer:

Check out this image:- DFS Traversal Tree

All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails.

Back Egdes: If there is an edge e(u,v) in G, such that e is not a tree edge(is not a part of the DFS tree) but u is the descendant of v in the DFS tree.

Forward edge: If there is an edge e(u,v) in G, such that v is the descendant of u but e is not a tree edge.

Cross edge: If there is an edge e(u,v) in G, such that neither of u or v are ancestors of each other.