HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMajor

Difference between cross edges and forward edges in a DFT

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
forwardedgesdftcrossdifferencebetweenand

Problem

In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).

There are some leftover edges connecting some of the other nodes. What is the difference between a cross edge and a forward edge?

From wikipedia:


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.

Doesn't an edge that is not used in the traversal that points from one node to another establish a parent-child relationship?

Solution

Wikipedia has the answer:

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.

This will explain the diagram:-

Forward edge: (u, v), where v is a descendant of u, but
not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Cross edge: any other edge. Can go between vertices in
same depth-first tree or in different depth-first trees. (layman)
It is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.(formal)

Context

StackExchange Computer Science Q#11116, answer score: 30

Revisions (0)

No revisions yet.