Breadth-first search explores a graph by distance layers. Depth-first search (DFS) explores it by following one path as far as possible before backing up. That order is less useful for shortest paths, but it exposes the structure of a graph: cycles, descendants and a valid ordering of tasks. Before analyzing it we must fix how a graph is stored, because the cost of every graph algorithm depends on that choice. The earlier unit on breadth-first search already assumed adjacency lists; here we justify the choice.
Representations
Let be a finite directed graph with vertices and arcs. An undirected edge is stored as two arcs.
Definition 13.2.1
(Adjacency matrix and adjacency lists)
The adjacency matrix is an array with if the arc exists and otherwise. The adjacency lists store, for each vertex , a list of the vertices with an arc .
| Operation | Matrix | Lists |
|---|---|---|
| Space | ||
| Is an arc? | ||
| List all out-neighbors of | ||
| Visit every arc once |
Here is the number of arcs leaving . A graph is sparse if , as is typical of road maps or dependency graphs, and dense if . For sparse graphs lists are far smaller and faster to traverse; for dense graphs the two have the same order of space, and the matrix offers constant-time arc queries. Traversals scan neighbors of each vertex, which is why lists are the default for DFS and BFS.
The algorithm
DFS keeps a color per vertex: white (undiscovered), gray (discovered but not finished, that is, currently on the recursion stack) and black (finished). A global clock records two timestamps: the discovery time and the finish time .
def dfs_all(graph):
n = len(graph)
color = [0] * n # 0 white, 1 gray, 2 black
d = [0] * n
f = [0] * n
clock = 0
finish_order = []
back_edges = []
def visit(u):
nonlocal clock
color[u] = 1
clock += 1
d[u] = clock
for v in graph[u]:
if color[v] == 0:
visit(v)
elif color[v] == 1:
back_edges.append((u, v))
color[u] = 2
clock += 1
f[u] = clock
finish_order.append(u)
for s in range(n):
if color[s] == 0:
visit(s)
return d, f, finish_order, back_edges
The outer loop restarts from every white vertex, so the whole graph is covered, producing a forest of DFS trees. Each vertex is visited once, because it is colored before its neighbors are examined, and each arc is examined once, when its tail is expanded. With adjacency lists the running time is ; with a matrix it would be . The recursion depth can reach , so a language with a small recursion limit needs an explicit stack for large paths.
Concept lensStructural
Gray vertices form the current path
At any moment the gray vertices are exactly the vertices on the tree path from the root of the current DFS tree down to the vertex being expanded, listed in order of discovery. Each call to visit adds its vertex to this path and removes it when the vertex turns black. Black vertices therefore form finished subtrees and white vertices are untouched. This gives a second reading of the same search: an arc into a gray vertex points back along the current path, while an arc into a black vertex points into a part of the graph that is already finished.
Structure of the search
Theorem 13.2.2
(Parenthesis property)
For any two vertices , the intervals and are either disjoint or one contains the other. Vertex is a DFS-tree descendant of exactly when .
Proof
(Calls nest like a stack)
All timestamps are distinct, so for we may assume . If , then was discovered while was still gray, that is, during the call visit(u). Calls nest like a stack, so visit(v) returns before visit(u) does, and . If instead , the intervals are disjoint. For the descendant statement: a descendant of is discovered inside visit(u), which gives the nesting. Conversely, if , then is discovered during visit(u), so it lies in the subtree of calls started from . The cases with and exchanged are symmetric.
When the arc is examined, its type is read off the color of and the timestamps:
- tree arc if is white (it becomes a child of );
- back arc if is gray ( is an ancestor of , possibly itself);
- forward arc if is black and ( is a non-child descendant);
- cross arc if is black and (no ancestry; finished before started).
Theorem 13.2.3
(Cycles and back arcs)
A finite directed graph contains a directed cycle if and only if a depth-first search of it finds a back arc.
Proof
(A back arc gives a cycle, and a cycle forces a back arc)
If there is a back arc , then is gray, so is an ancestor of (or ), and the tree path from to together with the arc is a cycle.
Conversely, let be a cycle and let be the vertex of with the smallest discovery time. Write as with (the case is a loop at ). When is discovered, are all white. We show by induction on that each is discovered during visit(w). This is clear for . Suppose it holds for . The call visit() lies inside visit(w) and examines the arc before it returns. If is white at that moment, it becomes a child of . Otherwise it has been discovered since time , because it was white then, and so during visit(w). In both cases is discovered during visit(w).
In particular is or a descendant of , and it examines the arc inside visit(w). At that moment has not finished, so is gray and the arc is a back arc.
Proof X-ray
Why the first-discovered vertex matters
The converse direction depends on one choice: is the vertex of discovered first. That choice does two jobs. It makes every other vertex of white at time , which starts the induction, and it guarantees that the closing arc into is examined while is still open, so is gray. Any other vertex of would not do. In , searched from 0, the vertex lies on the cycle but is discovered after 0, so at time the vertex 0 is gray rather than white and the white-path argument does not start. The back arc is , and it lands on the first-discovered vertex. The loop case needs no separate argument: and is gray while its own arcs are examined.
Theorem 13.2.4
(Topological order from finish times)
If the directed graph is acyclic, listing vertices in decreasing order of finish time gives a topological order: for every arc , appears before .
Proof
(Every arc finishes its head first)
Take an arc examined during visit(u). The vertex cannot be gray, since that would be a back arc and a cycle. If is white, it becomes a descendant of and finishes first, so . If is black, it has already finished, so again . In both cases finishes earlier than , so comes first in decreasing finish order.
Counterexample mode
Discovery order is not a topological order
It is tempting to list the vertices of a DAG by increasing discovery time. Take , , and search from 0, then from 2. The times are and , so discovery order is . The arc then points backwards, because 2 is discovered after 1. Decreasing finish time gives , and both arcs and point forwards. A later start can precede an earlier one, so only finish times carry the guarantee.
Worked examples
Worked example 13.2.5
(DFS on a six-vertex DAG)
Let the adjacency lists be , , , , , . Start at 0 with the clock at 0. Visit 0 (), then 1 (), then 3 (), then 5 (). Vertex 5 has no neighbors, so . Back in 3, ; in 1, . Return to 0 and examine 2: . Its first neighbor 3 is black with , so is a cross arc. Its second neighbor 4 is white: ; 4's neighbor 5 is black with a smaller discovery time, a cross arc; , , .
The finish order is , so decreasing finish time gives . Checking every arc: , , , , , , all go from earlier to later in this list. The tree arcs are , , , , .
Worked example 13.2.6
(A cycle found as a back arc)
Take , , , . DFS discovers with . At vertex 2 the first neighbor is 0, which is gray, so is a back arc. The gray vertices on the stack are , and following the stack from 0 to 2 and the back arc gives the cycle . The search continues: 3 is white with , ; then , , .
Adding a forward arc: if the graph also had the arc listed after , then when resumes after finishing , vertex 2 is black with , so is a forward arc.
Worked example 13.2.7
(A self-loop and several search trees)
Take , , . The outer loop starts at . Vertex 0 becomes gray with , and its only neighbor is 0 itself, which is gray, so is a back arc and the graph has a cycle of length one. Then . Vertex 1 is still white, so the outer loop starts a second tree: , the white neighbor 2 gives , , and . The result is a forest with two trees (rooted at 0 and at 1) and one back arc.
The edge cases are both visible here. A loop is a cycle that the color test detects with no special case, because is gray while its own arcs are examined. And a search from one start vertex would have missed vertices 1 and 2, which is why the outer loop is part of the algorithm.
Common mistakes
Counterexample mode
Undirected graphs: the parent is not a cycle
Store the undirected path with edges and as arcs in both directions and run the test "a gray neighbor means a cycle". At vertex 1 the neighbor 0 is gray, because it is the parent through which we arrived, so the test wrongly reports a cycle. In an undirected simple graph, skip the arc back to the tree parent once; any other gray neighbor then indicates a cycle. With parallel edges, a second edge to the parent really is a cycle, so skip the parent edge by edge identity, not by vertex.
Common mistake
(Reading the finish order forwards)
Take the single arc . A search from 0 gives , , , , so the finish order is , in which the arc points backwards. The topological order is the reverse, . On a graph with a cycle no topological order exists at all, so the theorem's hypothesis must be checked first, for instance by looking for a back arc.
Common mistake
(Marking a vertex only when it finishes)
The vertex must be colored when it is entered, not when it finishes. For , , if 0 were marked only at its end, then visit(1) would see 0 as white and call visit(0) again, and the recursion would never stop. Coloring on entry is what makes the gray state, and with it back-arc detection, possible.
Exercises with solutions
Quick check
(A directed graph has n = 1000 vertices and m = 3000 arcs. Compare the number of stored entries in a matrix and in adjacency lists, and the cost of a DFS on each.)
Solution · Answer
The matrix stores entries; the lists store list heads plus arc entries, about cells. DFS on lists takes steps; on the matrix each of the 1000 vertices scans a row of 1000 entries, so steps. The graph is sparse, so lists are better.
Quick check
(Run DFS from 0 on 0:[2], 1:[0], 2:[1,3], 3:[ ]. Give d, f, the arc types and any cycle.)
Solution · Answer
Visit 0 (), then 2 (), then 1 (). The arc finds 0 gray: a back arc. . Back at 2, vertex 3 is white: , . Then , . Arc types: , , are tree arcs and is a back arc. The cycle is . Every vertex is already black, so the outer loop starts nowhere else.
Quick check
(Intervals: A=[1,8], B=[2,5], C=[3,4], D=[6,7]. Classify the arcs A to C, C to A, D to B, A to D.)
Solution · Answer
The intervals show that is inside , which is inside , and is inside but disjoint from . For : is a descendant of but not its child (it lies inside ), so it is black when examined and : a forward arc. For : is an ancestor and gray: a back arc. For : is finished before starts (), so it is black with : a cross arc. For : is a child of because no vertex between them contains : a tree arc.
Quick check
(Find a topological order of 0:[3], 1:[3,4], 2:[4], 3:[ ], 4:[ ] using finish times, starting DFS at 0, 1, 2 in that order.)
Solution · Answer
From 0: , visit 3: , , then . From 1: ; 3 is black; visit 4: , ; . From 2: ; 4 is black; . Finish order ; reversed, . Every arc goes forward: (positions 4 and 5), (2 and 5), (2 and 3), (1 and 3).
Quick check
(In an undirected graph with edges {0,1} and {1,2}, why does the rule 'gray neighbor means cycle' give a false alarm, and how is it fixed?)
Solution · Answer
Each undirected edge is stored in both directions. When DFS reaches 1 from 0, the neighbor 0 is gray because it is the tree parent, not because of a cycle. The fix is to ignore the single arc that leads back to the parent through the edge by which the current vertex was discovered. Only a gray neighbor reached by a different edge signals a cycle.