Forward Edge in an Undirected Graph

Question

CLRS - Chapter 22

Theorem 22.10

In a depth-first search of an undirected graph G, every edge of G is either a tree edge or a back edge.

Proof Let (u,v) be an arbitrary edge of G, and suppose without loss of generality that u.d < v.d. Then the search must discover and finish v before it finishes u (while u is gray), since v is on u’s adjacency list. If the first time that the search explores edge (u,v), it is in the direction from u to v, then v is undiscovered (white) until that time, for otherwise the search would have explored this edge already in the direction from v to u. Thus, (u.v) becomes a tree edge. If the search explores (u,v) first in the direction from v to u, then (u,v) is a back edge, since u is still gray at the time the edge is first explored.

I most certainly understand the proof; but not quite convinced with the idea of forward edges.

In the above image, there is a forward edge from the first vertex to the third vertex (first row). The first vertex is the source.

As I understand DFS(S) would include a forward vertex 1 -> 3. (I am obviously wrong, but I need somebody to set me straight!)

Answer 1

It looks like you didn't include the definition of "forward edge," so I'll start with the definition I learned.

Assuming u.d < v.d, DFS labels the edge (u,v) a forward edge if when crossing the edge from u to v, v has already been marked as visited.

Because of that though, I claim that you cannot have forward edges in an undirected graph.

Assume for the sake of contradiction that it was possible. Therefore, the destination node is already marked as visited. Thus, DFS has already gone there and crossed all of the adjacent edges. In particular, you had to have already crossed that edge in the opposite direction. Thus, the edge has already been marked as a certain type of edge and thus won't be marked as a "forward edge".

Because of this, forward edges can only occur in directed graphs.

---

Now, just in case you mixed up "forward edges" and "tree edges", the edge you describe still isn't necessarily a tree edge. It is only a tree edge if when crossing, that was the first time you've visited the destination node. The easy way to think about it in undirected graphs is that when you traverse an edge, it is a back edge if the destination node has been reached already, and a tree edge otherwise.

Answer 2

I believe that what you are missing is some assumption about the order in which the algorithm would visit the different vertices.

Let's assume the algorithm visits the vertices in a lexicographic order. let's name the vertices this way:

 -------
|       |
S - A - B
|   |   |
C - D - E

In this case, the forward edges will be S->A, A->B, B->E, E->D, D->C. the rest of the edges are back edges.

Now let's rename the graph:

 -------
|       |
S - B - A
|   |   |
C - D - E

In this case, the forward edges will be S->A, A->B, B->D, D->C, D->E (note that S->A and S->B are not the same edge as in the previous example).

As you can see, the output depends on the order in which the algorithm selects the vertices. when the graph is anonymous, any output may be correct.

Answer 3

In the DFS tree of a general graph, there are TREE, FORWARD, BACK and CROSS edges.

In the DFS tree of an undirected graph, the would-be FORWARD edges are labeled as BACK edges. The would-be CROSS edges are labeled as TREE edges.

In both cases, the reason is that the edges can be traversed in both directions, but you first encounter them as BACK and TREE and second time as FORWARD and maybe CROSS and they are already labeled.

In a sense, an edge is both FORWARD and BACK and can be both CROSS and TREE, but is first found as BACK and TREE, repectively.