Depth-first Search

Depth-first search: The strategy followed by depth-first search is, as its name implies, to search "deeper" in the graph whenever possible. In depth-first search, edges are explored out of the most recently discovered vertex v that still has unexplored edges leaving it. When all of v's edges have been explored, the search "backtracks" to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source. This entire process is repeated until all vertices are discovered.

As in breadth-first search, whenever a vertex v is discovered during a scan of the adjacency list of an already discovered vertex u, depth-first search records this event by setting v's predecessor field π[v] to u. Unlike breadth-first search, whose predecessor subgraph forms a tree, the predecessor subgraph produced by a depth-first search may be composed of several trees, because the search may be repeated from multiple sources.^[2] The predecessor subgraph of a depth-first search is therefore defined slightly differently from that of a breadth-first search: we let G_π = (V, E_π), where

E_π = {(π[v], v) : v ∈ V and π[v] ≠ NIL}.

The predecessor subgraph of a depth-first search forms a depth-first forest composed of several depth-first trees. The edges in E_π are called tree edges.

As in breadth-first search, vertices are colored during the search to indicate their state. Each vertex is initially white, is grayed when it is discovered in the search, and is blackened when it is finished, that is, when its adjacency list has been examined completely. This technique guarantees that each vertex ends up in exactly one depth-first tree, so that these trees are disjoint.

Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex v has two timestamps: the first timestamp d[v] records when v is first discovered (and grayed), and the second timestamp f [v] records when the search finishes examining v's adjacency list (and blackens v). These timestamps are used in many graph algorithms and are generally helpful in reasoning about the behavior of depth-first search.

The procedure DFS below records when it discovers vertex u in the variable d[u] and when it finishes vertex u in the variable f [u]. These timestamps are integers between 1 and 2 |V|, since there is one discovery event and one finishing event for each of the |V| vertices. For every vertex u,

Vertex u is WHITE before time d[u], GRAY between time d[u] and time f [u], and BLACK thereafter.

The following pseudocode is the basic depth-first-search algorithm. The input graph G may be undirected or directed. The variable time is a global variable that we use for timestamping.

	DFS(G)
1  for each vertex u ∈ V [G]
2       do color[u] ← WHITE
3          π[u] ← NIL
4  time ← 0
5  for each vertex u ∈ V [G]
6       do if color[u] = WHITE
7             then DFS-VISIT(u)

	DFS-VISIT(u)
1  color[u] ← GRAY     ▹White vertex u has just been discovered.
2  time ← time  1
3  d[u] time
4  for each v ∈ Adj[u]  ▹Explore edge(u, v).
5       do if color[v] = WHITE
6             then π[v] ← u
7                         DFS-VISIT(v)
8  color[u] BLACK      ▹ Blacken u; it is finished.
9  f [u] ▹ time ← time  1

Figure 22.4 illustrates the progress of DFS on the graph shown in Figure 22.2.