Lesson · Graph Algorithms · Searching a graph

Depth-First Search and the Timestamps

A depth-first walk writes two numbers on each vertex: the step it was discovered and the step it was finished. Everything else this course reads off a walk comes from those two numbers. Whether one vertex is a descendant of another, whether the graph has a cycle, and which of four classes an arc belongs to are all decided by arithmetic on two intervals, and none of them needs a second pass.

Open the interactive lesson Practice

d[v] discovery, f[v] finish one counter, incremented twice per vertex tree the arc that discovered its head back d[head] < d[tail] and f[tail] < f[head]: the head is still open forward d[tail] < d[head] and f[head] < f[tail], and it is not the tree arc cross the two intervals are disjoint parenthesis theorem: two intervals nest or are disjoint, never overlap

Two times per vertex, and the four classes they decide

Core ideas

What this lesson establishes

One hard idea: the interval. The classes and the cycle test are both consequences of it, and neither is a separate thing to remember.

Two times, and the interval between them

A depth-first walk keeps one counter. It ticks when a vertex is first reached, giving d[v], and again when the walk has finished with every arc out of it, giving f[v]. The pair [d[v], f[v]] is an interval on the timeline, and v is open for exactly that stretch. On the lab's opening graph the walk starts at 1 and the six intervals come out [1, 8], [2, 7], [9, 12], [4, 5], [3, 6] and [10, 11] — twelve ticks for six vertices, because every vertex is opened once and closed once.

Four classes, each decided by arithmetic on two intervals

An arc from u to v is a tree arc when it is the one that discovered v; a back arc when v is still open, which is d[v] < d[u] with f[u] < f[v]; a forward arc when v is an already finished descendant of u; and a cross arc when the two intervals do not meet at all. Nothing else is consulted — not the drawing, not the order the arcs were typed, only the four numbers at the arc's ends.

A back arc is a cycle, and it is the whole test

If u has an arc to a vertex v that is still open, then v is an ancestor of u, so the tree path from v down to u exists; that path plus the arc is a cycle. Run it the other way and a cycle must produce a back arc, because the first vertex of the cycle the walk reaches stays open until every other vertex on it has been finished. So “acyclic” and “no back arc in one walk” are the same statement, and the second is checkable in one pass.

The material

One walk, and everything it writes down

The two times, the four classes, the theorem that the intervals obey, and the cycle test that falls out of it.

Definition · Discovery and finish times

A depth-first walk of a digraph keeps a counter starting at 0. On reaching an undiscovered vertex v it increments the counter and records d[v]; after every arc out of v has been considered it increments the counter again and records f[v]. When the walk from one root runs out of reachable vertices it restarts at the lowest-numbered undiscovered vertex, so the tree arcs form a FOREST and not necessarily a tree.

The counter is shared across the whole forest, which is what makes the times comparable between vertices that were never on the same walk. On n vertices it ends at 2n, always, because each vertex contributes exactly one tick when it opens and one when it closes.

Definition · The four classes of an arc

Relative to one completed walk, an arc (u, v) is a tree arc if v was discovered by it; a back arc if v is a proper ancestor of u in the forest; a forward arc if v is a proper descendant of u and the arc is not the tree arc; and a cross arc otherwise. The four are exhaustive and exclusive, so every arc gets exactly one label.

The definition names ancestry, and ancestry is read off the times: v is a descendant of u exactly when d[u] < d[v] and f[v] < f[u]. That is the whole of the implementation. The lab prints, for every arc, the class and the comparison that settled it.

Example · Eight arcs, one walk, all four classes

The lab opens on the arcs 1>2, 1>4, 2>5, 4>2, 5>4, 3>5, 3>6, 6>3 with the walk starting at 1. The walk goes 1, 2, 5, 4, closes all four, then restarts at 3 and reaches 6, giving d = 1, 2, 9, 4, 3, 10 and f = 8, 7, 12, 5, 6, 11. Classified from those numbers: 1>2, 2>5, 5>4 and 3>6 are tree arcs; 4>2 and 6>3 are back; 1>4 is forward, because 4 is a finished descendant of 1; and 3>5 is cross, because [9, 12] and [3, 6] do not meet. Four, two, one and one, on eight arcs.

Two of those deserve a second look. 1>4 is forward rather than tree because the walk reached 4 first through 2 and 5 — the arc 1>4 was examined later, found 4 already finished, and discovered nothing. And 3>5 is cross although 3 and 5 are both on the same picture: the walk had closed 5 at step 6 before it opened 3 at step 9, so neither is an ancestor of the other.

Theorem · The parenthesis theorem

For any two vertices u and v of one walk, exactly one of three things holds: the intervals [d[u], f[u]] and [d[v], f[v]] are disjoint and neither vertex is an ancestor of the other; [d[v], f[v]] lies wholly inside [d[u], f[u]] and v is a descendant of u; or the reverse. The intervals never partly overlap.

Suppose d[u] < d[v]. When v is discovered, u is either still open or already closed.

If u is still open then the walk reached v from inside u, so v is a descendant of u; and the walk cannot close u while v is open, because closing u means every arc out of it, and every recursive call below it, has returned. So f[v] < f[u] and the intervals nest.

If u is already closed then f[u] < d[v], so the intervals are disjoint, and neither can be an ancestor of the other: an ancestor is open for the whole of its descendant's interval. A partial overlap would need d[u] < d[v] < f[u] < f[v], which is the first case with v closing after u, and that case has just been ruled out.

□

The lab does not quote that theorem, it checks it. On the opening graph there are 15 pairs of vertices; the panel reports that 7 of them nest, 8 are disjoint, and 0 overlap without nesting, and it separately confirms that nesting and descent agree on every pair. Change the graph and it recounts.

The class of an arc is a fact about the walk, not about the graph

Start the same eight arcs at vertex 3 instead of vertex 1. The times become d = 11, 4, 1, 3, 2, 8 and f = 12, 5, 10, 6, 7, 9, and the counts change: four tree arcs and two back arcs as before, but now 0 forward arcs and 2 cross arcs. The arc 1>4 that was forward is now cross. Move the slider in the lab and watch the table rewrite itself.

What does NOT change is the back count. It is 2 from either root, and it has to be: a back arc means a cycle, a cycle is a property of the arcs and not of the walk, and this graph has cycles. The lab's status line therefore reads acyclicity off the back count alone and says nothing about the other three.

Read the same arcs undirected and two classes disappear

Switch the lab's reading to undirected and the counts for forward and cross both come out 0, on this graph and on every graph the panel has been given. The reason is that an undirected edge is met from whichever end the walk reached first: if the far end is already discovered it cannot have been finished, because the walk would have crossed this very edge and finished this end first. So the far end is an open ancestor, which is a back edge. Forward and cross are phenomena of direction.

Finally the cost. On the opening graph the panel reports 6 vertex visits and 8 arc reads, and those two numbers are what Θ(V + E) names: each vertex is opened once and each arc is examined once from its tail. The count is for this graph. The bound is the claim that on every graph the two figures are exactly V and E, and it is proved by the walk's own structure — a vertex is discovered once because discovery sets d, and an arc is read once because the loop over a vertex's arcs runs once.

Interactive

Discovery and finish times, and the four edge classes

One depth-first walk; the intervals nest exactly when one vertex is inside the other

Type a graph, then move the walk's starting point

The walk runs in your browser and every class is decided from the two times at the arc's ends, never from the drawing. The parenthesis theorem is checked on every pair of vertices rather than stated, and the reading can be switched to undirected to watch two of the four counts fall to zero.

Worked example

Arcs, as tail>head

Start the walk at1

Read the arcs as

Draw heavy the arcs that are

Tree arcs—

Back arcs—

Forward arcs—

Cross arcs—

Pairs whose intervals nest—

Pairs that overlap without nesting—

An arc is tail>head and labels start at 1. The class of an arc is decided by the times at its ends and nothing else: tree when the arc is the one that discovered its head, back when the head is still open, forward when the head is a finished descendant, cross otherwise. Switch the reading to undirected and watch two of the four counts go to zero.

Method

Reading a walk, rather than re-running it

Write the times down first. Every question after that is arithmetic on two of them.

Record both times, not just the order

A list of the order vertices were visited in loses the finish times, and the finish times are what every classification uses. Write the interval beside each vertex as the walk closes it.

Classify an arc from its two intervals

Nested with the head inside means forward or tree; nested with the tail inside means back; disjoint means cross. Then separate tree from forward by asking which arc actually discovered the head, which is the one thing the times alone cannot tell you.

Answer the cycle question with the back count and nothing else

Do not look for a cycle in the drawing and do not count the other three classes. One back arc is a cycle and no back arc is acyclicity, and both directions of that are proved, so one number settles it.

Change the root before you generalise

Any claim that survives one starting vertex and not another is a claim about the walk. The lab makes this cheap: move the slider, and if the number you were about to write down moves with it, it was not a property of the graph.

Times, classes, and what each one settles

Score 0 / 0

Choose the answer you can justify.

The opening graph, walked by hand

The arcs are 1>2, 1>4, 2>5, 4>2, 5>4, 3>5, 3>6, 6>3 and the walk starts at 1. Arcs out of a vertex are taken in the order they were typed.

tick event d / f written 1 open 1 d[1] = 1 2 1>2 discovers 2, open 2 d[2] = 2 3 2>5 discovers 5, open 5 d[5] = 3 4 5>4 discovers 4, open 4 d[4] = 4 5 4>2 finds 2 open -> BACK; close 4 f[4] = 5 6 close 5 f[5] = 6 7 close 2 f[2] = 7 8 1>4 finds 4 finished -> FORWARD; close 1 f[1] = 8 9 restart at 3, open 3 d[3] = 9 10 3>5: [9,12] and [3,6] disjoint -> CROSS 10 3>6 discovers 6, open 6 d[6] = 10 11 6>3 finds 3 open -> BACK; close 6 f[6] = 11 12 close 3 f[3] = 12 intervals 1:[1,8] 2:[2,7] 3:[9,12] 4:[4,5] 5:[3,6] 6:[10,11] classes tree 4 back 2 forward 1 cross 1 on 8 arcs pairs 15 checked: 7 nest, 8 disjoint, 0 overlap

The forest has two roots, 1 and 3, because nothing reaches 3 from 1. That is why the definition says forest: a single walk from a single root would have left three vertices with no times at all, and the restart rule is what makes d and f total functions.

Notice that tick 10 does two things. The arc 3>5 is examined and classified without the counter moving, because examining an arc that discovers nothing is not an event the counter records. Only openings and closings tick, which is why the last finish time is 2n exactly.

For a faded rehearsal, delete the arc 3>5 and predict all twelve numbers before running it. The supplied first move is this: removing 3>5 removes the only cross arc and changes no time at all, because that arc discovered nothing and the counter never moved for it. Say what the four counts become, then check them — and then delete 1>4 instead and say why that one also leaves every time alone.

Common mistakes

Treating the classification as a property of the graphOnly the tree and back counts are stable in the way readers expect, and even the tree arcs change which arcs they are. The lab's root slider is there to make this cheap to check: on the opening graph, starting at 1 gives one forward arc and one cross arc, and starting at 3 gives none and two. Any sentence beginning “the forward arcs of this graph” is already wrong.

Hunting for a cycle in the pictureThe drawing is a convenience and the walk is the algorithm. A reader who looks for a loop by eye on twelve vertices will miss one, and worse, will have no procedure when the graph has fifty. One completed walk answers it with a count, and the answer is proved in both directions rather than spotted.

Reading a cross arc as evidence of a second componentA cross arc only says the two intervals are disjoint. On the opening graph the arc 3>5 is cross and 5 is perfectly reachable from 3 — the walk simply finished with 5 before it ever opened 3. Reachability and ancestry in one walk's forest are different questions, and the times answer the second.

Check your understanding

✓

Finish when you can classify every arc of a graph you have not seen before, from the times alone.

You should be able to run the walk by hand and record both times, name the class of an arc by comparing two intervals, say why zero back arcs settles acyclicity while zero cross arcs settles nothing, and predict which counts will move when the root moves.

Note: Everything in the rest of this module is these two numbers used again. “Topological Order” takes the finish times in decreasing order and gets a schedule for tasks; “Bridges and Cut Vertices” adds one more number per vertex to the same walk; and “Strongly Connected Components” runs the walk twice, the second time on the reversed arcs, using the first walk's finishing order as its schedule.