Classification of Edges in DFS — Directed Graphs

For a directed graph,  every edge encountered by DFS into four types:

1. Tree edge
2. Back edge
3. Forward edge
4. Cross edge

This classification is based on the relationship between the two vertices in the DFS forest.

---

1. Tree Edge

A tree edge is an edge that DFS uses to discover a new vertex.

Suppose DFS is exploring vertex u and encounters a WHITE vertex v:

u → v

Since v has not been discovered before, DFS executes:

v.π = u
DFS-VISIT(G, v)

Therefore, (u,v) becomes a tree edge.

Example

        A
        |
        B
        |
        C

If DFS discovers the vertices in the order:

A → B → C

then:

(A,B) = Tree edge
(B,C) = Tree edge

Tree edges form the DFS tree.

How to identify it

When DFS examines (u,v):

v.color = WHITE

Therefore:

WHITE destination⇒Tree edge​

---

2. Back Edge

A back edge is an edge from a vertex to one of its ancestors in the DFS tree.

Consider:

        A
        ↓
        B
        ↓
        C
        ↓
        D

Suppose the graph also contains:

D → B

Then:

D → B

is a back edge, because B is an ancestor of D.

        A
        |
        B ←──────┐
        |        |
        C        |
        |        |
        D ───────┘

The edge goes back toward an ancestor.

How to identify it

When DFS examines (u,v) and:

v.color = GRAY

then v is currently active in the DFS recursion.

The GRAY vertices form the current chain of ancestors.

Therefore:

GRAY destination⇒Back edge​

---

3. Back Edge and Cycles

This is one of the most important applications of edge classification.

Consider:

A → B → C
↑       |
|_______|

The edge:

C → A

is a back edge because A is an ancestor of C.

Therefore, the graph contains a cycle:

A → B → C → A

Hence, for a directed graph:

Back edge⇒Cycle​

This gives us a simple DFS-based method for detecting cycles in directed graphs.

---

4. Forward Edge

A forward edge is a nontree edge from a vertex to one of its proper descendants in the DFS tree.

Consider:

        A
       / \
      B   C
      |
      D

Suppose the original graph contains:

A → D

but DFS discovered D through B:

A → B → D

Then:

A → D

is not a tree edge, because it was not used to discover D.

However, D is a descendant of A.

Therefore:

A→D is a forward edge​

The important distinction is:

Tree edge: ancestor discovers descendant.

Forward edge: ancestor points to descendant, but that edge was not used for discovery.

---

5. How to Identify a Forward Edge

When DFS encounters a BLACK vertex, the edge can be either a forward edge or a cross edge.

We can distinguish them using discovery times.

For a forward edge:

$$u.d<v.d$$

because u was discovered before its descendant v.

Therefore:

u.d<v.d⇒Forward edge​

provided the edge is not a tree edge.

---

6. Cross Edge

A cross edge is a nontree edge that connects vertices where neither vertex is an ancestor of the other.

For example:

          A
         / \
        B   C
        |   |
        D   E

Suppose the original graph contains:

D → E

D and E belong to different branches of the DFS tree.

Neither is an ancestor of the other.

Therefore:

D→E is a cross edge​

Cross edges can also occur between vertices belonging to different DFS trees.

---

7. Identifying a Cross Edge

If the destination vertex is BLACK, we know the edge is either forward or cross.

If:

$$u.d>v.d$$

then v was discovered before u.

In this situation, for a directed graph, the edge is a cross edge.

Thus:

u.d>v.d⇒Cross edge

8. DFS Color-Based Classification

This is the particularly useful CLRS observation.

When DFS first examines an edge (u,v):

Color of v	Edge type
WHITE	Tree edge
GRAY	Back edge
BLACK	Forward or Cross edge

For BLACK vertices, use discovery times:

Condition	Edge
u.d < v.d	Forward edge
u.d > v.d	Cross edge

9. DFS Edge Classification and Applications

Application 1: Detecting Cycles

For a directed graph, a back edge indicates a cycle.

Example:

A → B → C
↑       |
└───────┘

C → A is a back edge.

Therefore:

Back edge⇒Directed cycle​

This is useful for detecting:

• cyclic dependencies
• deadlock-like dependency structures
• cycles in prerequisite graphs
• whether a directed graph is a DAG

---

Application 2: Topological Sorting

A directed graph has a topological ordering only if it is a DAG (Directed Acyclic Graph).

DFS can be used to detect a back edge.

Therefore:

DFS
 ↓
Back edge?
 ↓
YES → Cycle → Not a DAG → No topological ordering

If there is no back edge, the directed graph is acyclic, and DFS finishing times can be used to construct a topological ordering.

---

Application 3: Dependency Analysis

Consider:

Course A → Course B
Course B → Course C
Course C → Course D

The edges represent prerequisite relationships.

DFS can be used to determine whether the dependency graph contains a cycle.

For example:

A → B → C → A

creates a back edge and indicates an invalid circular dependency.

---

Application 4: Understanding Graph Structure

The four edge types reveal the structure of a directed graph:

Tree       → DFS discovery relationship
Back       → Ancestor relationship / cycle
Forward    → Descendant relationship
Cross      → Independent branches or DFS trees

This classification becomes particularly useful in more advanced graph algorithms. 

10. A Very Important Point About Directed Graphs

For a directed graph, all four types are possible:

Tree, Back, Forward, Cross​

This is different from an undirected graph, where DFS produces only tree edges and back edges.