# Understanding the “ordering of the four types of edges” in DFS

The following is Exercise 22.3-6 from CLRS (Introduction to Algorithms, the 3rd edition; Page 611).

Show that in an undirected graph, classifying an edge $$(u,v)$$ as a tree edge or a back edge according to whether $$(u,v)$$ or $$(v,u)$$ is encountered first during the depth-first search is equivalent to classifying it according to the ordering of the four types in the classification scheme.

Problem: What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to? What is supposed to prove?

The classification scheme is defined on page 609:

We can define four edge types in terms of the depth-first forest $$G_{\pi}$$ produced by a depth-first search on $$G$$:

1. 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)$$.
2. Back edges are those edges $$(u,v)$$ connecting a vertex $$u$$ to an ancestor $$v$$ in a depth-first tree.
3. Forward edges are those nontree edges $$(u,v)$$ connecting a vertex $$u$$ to a descendant $$v$$ in a depth-first tree.
4. 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 they can go between vertices in different depth-first trees.

Consider the figure below. Suppose that a DFS starts from node $$u$$ and travels along $$(u,x)$$ first and then $$(x,v)$$. Both $$(u,x)$$ and $$(x,v)$$ are tree edges.

What about the edge $$(v, u)$$? It should be a back edge according to the classification scheme in the textbook. How is $$(v,u)$$ classified as back edge according to the classification in the exercise?

Is $$(v,u)$$ a tree edge while $$(u,v)$$ a back edge according to the definition in the exercise? This is strange, because in an undirected graph, $$(u,v)$$ and $$(v,u)$$ refer to the same edge.

• The ordering refers to the order "tree edges, back edges, forward edges, cross edges". – Yuval Filmus Oct 21 '18 at 8:21
• @YuvalFilmus Thanks. However, I am still confused. I have added an example to explain my confusion. Could you please have a look at it? – hengxin Oct 22 '18 at 5:41

I have reviewed section 22.3, "Depth-first search" a couple of times.

"What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $$1 \prec 2 \prec 3 \prec 4$$. In other words, tree edges precede back edges, which precede forward edges, which precede cross edges.

What is supposed to prove?

Suppose we have done a depth-first search $$S$$ on an undirected graph $$G$$ that has produced the depth-first forest $$G_\pi$$ as describe in the textbook.

An edge $$e=\{u,v\}=\{v,u\}$$ can be represented by either the directed edge $$(u,v)$$ or the directed edge $$(v,u)$$. Note that $$(u,v)\not=(v,u)$$. Both $$(u,v)$$ and $$(v,u)$$ will be explored during $$S$$. There are two methods to classify $$e$$ with respect to $$S$$.

1. $$e$$ is classified as the earliest type of edge (according to that ordering) which either $$(u,v)$$ or $$(v,u)$$ can be classified as.
More specifically, if either $$(u,v)$$ or $$(v,u)$$ is classified as a tree edge, then $$e$$ is classified as a tree edge. Otherwise, $$e$$ is classified as a back edge. Note that at least one of $$(u,v)$$ and $$(v,u)$$ must be classified as either tree edge or back edge (theorem 22.10 of the book).

2. If $$(u,v)$$ is discovered earlier than $$(v,u)$$, then $$e$$ is the same type of edge as $$(u,v)$$. If $$(v,u)$$ is discovered earlier than $$(u,v)$$, then $$e$$ is the same type of edge as $$(v,u)$$.

That exercise asks readers to prove the above two classifying methods are equivalent. That is, $$e$$ is classified as type $$X$$ by the first method if and only if $$e$$ is classified as type $$X$$ by the second method, given any edge $$e$$ and any type $$X$$.

(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)

Let us take a look at the example given in the question.

Here is the relevant part of running DFS-VISIT $$(G,u)$$.

1. $$u.d = 1$$
2. $$x.\pi = u$$
3. $$x.d = 2$$
4. $$v.\pi = x$$
5. $$v.d = 3$$
6. Now we discover edge $$(v,u)$$, which connects $$v$$ to $$u$$, which is an ancestor of $$v$$ since $$v.\pi=x$$ and $$x.\pi = u$$. That is, $$(v,u)$$ is a back edge. This is the first time edge $$e$$ is discovered. So $$e$$ is a back edge according to second classifying method.
7. $$v.f = 4$$
8. $$x.f = 5$$
9. Now we discover edge $$(u,v)$$, which connects $$u$$ to its descendant $$v$$. This edge $$(u,v)$$ is classified as a forward edge. Since $$(v,u)$$ is classified as a back edge, a type of edges that precedes a forward edge, $$e$$ is a back edge according to the first classifying method.
10. $$u.f = 6$$

We just saw that $$e$$ is classified as the same type of edge according to either classifying method. That exercise asks readers to prove that is not a coincidence.

• Thanks. However, I am still confused. I have added an example to explain my confusion. Could you please have a look at it? – hengxin Oct 22 '18 at 5:40
• :) I am waiting (both on the Internet and in my university). – hengxin Oct 22 '18 at 6:01
• OK. Now I think I understand it. I have misunderstood the statement in the exercise as "classifying $(u,v)$ as a tree edge if $(u,v)$ is encountered before $(v,u)$, otherwise classifying it a back edge". To make sure: Each edge $\{u,v\}$ will be encountered twice in a DFS. The definition in the text uses the first "type" according to the ordering, and that in the exercise uses the type the first "time" the edge is classified. Is this right? – hengxin Oct 22 '18 at 12:40
• Yes, that is correct. Either the earlier "type" or the first "time". That is, the first time always goes together with the earlier type. – John L. Oct 22 '18 at 12:54
• @JohnL. " 1. The earliest type of edge (according to that ordering) as which either $(u,v)$ or $(v,u)$ can be classified, then $e$ is classified as that kind of edge. " Your answer is great but could you please elaborate the above definition. I feel that somewhere the entire meaning is not conveyed to me. And pardon me for asking a doubt in an old question's answer. Thank you... – Abhishek Ghosh Aug 5 at 16:10