The Algorithm Design Manual Second Edition

5.9

Applications of Depth-First Search

As algorithm design paradigms go, a depth-first search isn’t particularly intimidat-

ing. It is surprisingly subtle, however meaning that its correctness requires getting

details right.

The correctness of a DFS-based algorithm depends upon specifics of exactly

when we process the edges and vertices. We can process vertex v either before we

have traversed any of the outgoing edges from v (process vertex early()) or after

we have finished processing all of them (process vertex late()). Sometimes we

will take special actions at both times, say process vertex early() to initialize a

vertex-specific data structure, which will be modified on edge-processing operations

and then analyzed afterwards using process vertex late().

In undirected graphs, each edge (x, y) sits in the adjacency lists of vertex x

and y. Thus there are two potential times to process each edge (x, y), namely when

exploring x and when exploring y. The labeling of edges as tree edges or back edges

occurs during the first time the edge is explored. This first time we see an edge is

usually a logical time to do edge-specific processing. Sometimes, we may want to

take different action the second time we see an edge.

But when we encounter edge (x, y) from x, how can we tell if we have previously

traversed the edge from y? The issue is easy if vertex y is undiscovered: (x, y)

if (finished) return;

p = p->next;

}

process_vertex_late(v);

time = time + 1;

exit_time[v] = time;

processed[v] = TRUE;

}

---

5 . 9

A P P L I C A T I O N S O F D E P T H - F I R S T S E A R C H

173

Figure 5.11: An articulation vertex is the weakest point in the graph

I find that the subtlety of depth-first search-based algorithms kicks me in the

head whenever I try to implement one. I encourage you to analyze these implemen-

tations carefully to see where the problematic cases arise and why.