Depth-first search: discovery and finish times, edge classification

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• BFS uses which data structure? from Lesson 6.1.1
• Stack order? from Lesson 0.2.1
• Number of edges of a tree on n vertices? from Lesson 0.2.3

1 · The Hook

🎣

Solving a maze, you walk down one corridor as far as it goes and back up only at a dead end. That is depth-first search (DFS). Recording when each vertex is first reached and when it is finished turns DFS into a tool that detects cycles, sorts tasks and finds components, which is why GATE asks for discovery and finish times and edge types.

2 · Predict First

🤔

DFS from A on the six-town graph, always going to the alphabetically first unvisited neighbour. In what order are the towns discovered?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

A → B (first neighbour of A) → C (B's first unvisited) → D (C's first unvisited) → E → F: A, B, C, D, E, F, a single long path.

The algorithm (with times)

DFS(G):
    for each vertex u (alphabetical): if u is white: VISIT(u)
VISIT(u):
    time = time + 1; d[u] = time; colour u grey      // discovered
    for each neighbour v of u (alphabetical):
        if v is white: parent[v] = u; VISIT(v)
    time = time + 1; f[u] = time; colour u black     // finished

White = not yet discovered, grey = discovered but not finished (on the recursion stack), black = finished. Times run 1 … 2V. Cost Θ(V + E) with lists.

Parenthesis theorem

For any two vertices, the intervals [d, f] are either nested or disjoint. v is a descendant of u in the DFS forest exactly when d[u] < d[v] < f[v] < f[u].

Edge classification (directed graph), edge u → v when explored

• A directed graph has a cycle exactly when DFS finds a back edge.
• In an undirected graph DFS produces only tree and back edges.

Worked example (directed graph below, alphabetical order)

u: 1/8, v: 2/7, y: 3/6, x: 4/5, w: 9/12, z: 10/11. Tree: u→v, v→y, y→x, w→z. Back: x→v, z→z (self-loop). Forward: u→x. Cross: w→y.

4 · Visual

DFS of a directed graph with d/f times. T tree (red), B back (dashed), F forward, C cross. z also has a self-loop z→z, a back edge (not drawn).

5 · Worked Examples

Example 1 Easy

In the six-town DFS from A, what are d[C] and f[C]?

Solution

Discovery order A, B, C, D, E, F gives d = 1 … 6; F finishes at 7, E 8, D 9, C 10: d[C] = 3, f[C] = 10.

Example 2 Medium

In the six-town DFS, how many back edges are there?

Solution

Tree edges A–B, B–C, C–D, D–E, E–F (5 of the 9); the other 4 (A–C, B–D, C–E, D–F) are back edges.

Example 3 GATE

In a DFS of a directed graph, d[p] = 3, f[p] = 10, d[q] = 5, f[q] = 8. Edge p → q is not a tree edge. Its type?

Solution

3 < 5 < 8 < 10: q is a descendant of p, so p → q is a forward edge.

6 · GATE Traps

⚠️

• d and f together use times 1 … 2V; each vertex gets two stamps.
• Back edge ⇔ cycle (directed). A self-loop counts as a back edge.
• Undirected graphs: only tree and back edges, never forward or cross.
• Cross edges go from a later-discovered vertex to an earlier finished one (d[v] < d[u]).

7 · Memory Hook

🧠

"Grey means on the stack: an edge to grey closes a cycle."

8 · Connect the Dots

DFS times are not just bookkeeping. The next lesson sorts a DAG by finish time, detects cycles, and counts connected and strongly connected components.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFinish time

In the lesson's directed DFS, what is f[v]?

Numerical answer: ________

Q2NAT1 markBack edges

In the lesson's directed DFS, how many back edges are there (count the self-loop)?

Numerical answer: ________

Q3MCQ1 markCycle test

A directed graph contains a cycle exactly when its DFS finds:

• (A) a forward edge
• (B) a tree edge
• (C) a back edge
• (D) a cross edge

Q4NAT2 marksTimes

In the six-town DFS from A (alphabetical), what is f[A]?

Numerical answer: ________

Q5MSQ2 marksUndirected DFS

In a DFS of an undirected graph, which edge types can occur?

• (A) Tree
• (B) Cross
• (C) Back
• (D) Forward

10 · Rule Card

• DFS: d[u] on discovery, f[u] on finish; times 1 … 2V; Θ(V + E).
• Parenthesis: intervals nested or disjoint; descendant ⇔ d[u] < d[v] < f[v] < f[u].
• Tree (white), back (grey), forward (black descendant), cross (black, d[v] < d[u]).
• Directed cycle ⇔ back edge. Undirected: only tree and back.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

depth-first searchdiscovery time dfinish time fwhite, grey, blackparenthesis theoremtree, back, forward and cross edgescycle iff back edge

12 · Answer Vault