20
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Related: cs.stackexchange.com/questions/99988/… seeks to establish an algorithm which, for directed graph, will prefer to make forward edges, instead of cross edges, during depth-first search. $\endgroup$
    – pfalcon
    Commented Nov 14, 2018 at 7:15

3 Answers 3

Reset to default
30
$\begingroup$

Wikipedia has the answer:

enter image description here

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)

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Why is it not impossible for 6 to have been traversed first (right side first)? If that had happened, what would the 2->3 edge have been called? $\endgroup$
    – soandos
    Commented Apr 8, 2013 at 1:25
  • $\begingroup$ @soandos, I suggest you take the time yourself to trace the algorithm. Assuming the Wikipedians didn't make a mistake, the image describes a bona fide run of DFS on this graph, and so there is a way to fit the algorithm into this trace. The types of edges are described clearly enough in Wikipedia, and you can also consult this example. $\endgroup$
    – Yuval Filmus
    Commented Apr 8, 2013 at 1:27
  • $\begingroup$ I understand that this is a valid way of doing a DFS. I am simply asking what if it was done the other way. $\endgroup$
    – soandos
    Commented Apr 8, 2013 at 3:38
  • $\begingroup$ Then the results would be different. I'm sorry, you'd have to work it out yourself. $\endgroup$
    – Yuval Filmus
    Commented Apr 8, 2013 at 4:53
  • 3
    $\begingroup$ @soandos In general, there can very well be multiple DFS traversals. The notions used here are relative to one given traversal and will differ for multiple traversals. $\endgroup$
    – Raphael
    Commented Apr 8, 2013 at 14:38
12
$\begingroup$

A DFS traversal in an undirected graph will not leave a cross edge since all edges that are incident on a vertex are explored.

However, in a directed graph, you may come across an edge that leads to a vertex that has been discovered before such that that vertex is not an ancestor or descendent of the current vertex. Such an edge is called a cross edge.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Aporov, Thanks for the response. It still seems to me that when you get to vertex 6 in the DFS as diagramed in Wikipedia, you have three edges to traverse from 6. At that point, vertex 6 is "current". Eventually you are going to traverse the edge to vertex 3. While 3 has been visited already, nonetheless since there is an edge from 6 to 3, then 3 is a descendant of the "current" vertex 6. If that is so, it violates the definition of a cross edge. There must be something more to the definition that isn't being made very explicit. $\endgroup$
    – user46773
    Commented Feb 23, 2016 at 21:32
  • $\begingroup$ In fact, DFS only contains either tree edges for back edges (Intro to Algorithms Thm. 22.10). $\endgroup$
    – jrhee17
    Commented Aug 21, 2016 at 14:41
3
$\begingroup$

In a DFS traversal, nodes are finished once all their children are finished. If you mark the discover and finish times for each node during traversal, then you can check to see if a node is a descendant by comparing start and end times. In fact any DFS traversal will partition its edges according to the following rule.

Let d[node] be the discover time of node, likewise let f[node] be the finish time.

Parenthesis Theorem For all u, v, exactly one of the following holds:
1. d[u] < f[u] < d[v] < f[v] or d[v] < f[v] < d[u] < f[u] and neither of u and v is a descendant of the other.

  1. d[u] < d[v] < f[v] < f[u] and v is a descendant of u.

  2. d[v] < d[u] < f[u] < f[v] and u is a descendant of v.

So, d[u] < d[v] < f[u] < f[v] cannot happen.
Like parentheses: ( ) [], ( [ ] ), and [ ( ) ] are OK but ( [ ) ] and [ ( ] ) are not OK.

For example, consider the graph with edges:
A --> B
A --> C
B --> C

Let the order of visiting be represented by a string of the nodes labels, where "ABCCBA" means A --> B --> C (finished) B (finished) A (finished), similar to ((())).

So "ACCBBA" could be a model for "(()())".

Examples:
"CCABBA" : Then A --> C is a cross edge, since the CC is not inside of A.
"ABCCBA" : Then A --> C is a forward edge (indirect descendant).
"ACCBBA" : Then A --> C is a tree edge (direct descendant).

Sources:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.